When you want to write a recovery code (ie. a computation heavy code needing to be heavily optimized) you shouldn't go through the simple route writing a "normal" code like what you'd write for a normal function that encodes/decodes Base58 keys. Instead you should find the bottlenecks in your code and try to go around them by finding alternative computation route that perform faster.

I'm not a python expert but for example in your code when you are replacing * with random chars and then convert it to a key in this line:
you are adding a big bottleneck that slows your code specially since you are throwing and catching an exception which adds additional computational cost.
Changing that code and doing the conversion from base58 in your own code would significantly improve your speed. Of course when optimizing you must always perform benchmarks on your code and the changes you make so that you don't make it slower. And you should add tests so that you don't introduce bugs.