I agree that pattern-based redirects as implemented by mod_rewrite or mod_alias' RedirectMatch can probably be used to greatly reduce the number of redirect directives needed.
However, to answer your question a bit more directly: The server performance impact of 5000 lines of code will depend on how many requests per second you get, how fast your server's CPU is, how much physical memory it has, and if it is shared, how many other sites it is shared with, and how busy they are.
If you're on a fast dedicated server with a lot of memory, you may not notice a performance problem until you reach several thousand requests per minute. If you are on heavily-shared hosting on a typical server, then you may have problems handling only one or two dozen requests per second...
Realize that every one of these redirect directives will be processed for each and every HTTP request to your server -- For every page, image, script, multimedia file, or stylesheet request. That is, unless you write the code to prevent this by making some of the code conditional (e.g. "skip this code except for .html page requests").
I would not recommend implementing 5000 redirects, either from a server-performance perspective, or from an SEO standpoint; You may destroy your site pages' ranking in search engines by making such a large change so suddenly.