Hi,
Well looking for the right redirect in table with 3000 records shouldn't be a problem for most servers, so I'd suggest to first try if the slowdown is really caused by adding the redirects (you could back up your jos_sefmoved table and clear it to see if there's a difference) and if it is, check your server configuration.