Limit # page version creation, paths under which version can be created implicitly and age of versions. You could even choose to stop implicit version creation (after evaluating pros/cons) and move into manual mode that would be done by authors explicitly for specific project(s).That depends on your requirements.
Limit the age of versions so that you have less numbers of purge activities based on your requirements/compliance etc.
Schedule the purge job to run on off-business hours when no author is creating versions. That should not slow down the system.
I'm not aware of any patch for same. DayCare ticket is your best bet for patches.
couple of links in case you want to proceed with a custom solution -