I fear the answer here is that redirecting will just never come with good performance. Especially doing it via PHP, because then it’s handled rather late.
You could think about doing it via apache in particular the .htaccess file, which intercepts way earlier, before PHP/WordPress even come into play. Which will be better, but of course it still will be a redirect. But as @birgire pointed out in his comment, you need the concrete/exact rules, so this isn’t very practical.
Another idea, doing some javascript “magic”, same comment.
If you ask me it’s not worth it, either you redirect or you don’t, just decide.