Why delete old redirects?
Whether to keep redirects is an SEO question. Do you have good search results on Google which you don't want to loose. Or you have external sites or even print stuff that point to your old URLs. Then you have to keep them.

If all this is not true, you can safely delete you old redirects.

About the DB:

The redirects are stored in the url_alias table. It has two indexes for the mapping from nid to redirect url and from redirect url to nid. This means that reading is fast even if you have thousands of redirects.

If you are creating a lot of redirects this can get slow. But this will not hit you for a few thousand redirects. If you have millions you have to dive into MySql details (or whatever DB system you are using) and find what you can do about it. Since you are only adding records to the DB table, there's a lot of DB tuning stuff that can help you.