primes are fairly sparse so on average you have to generate quite a few random numbers to find a single prime

The density of primes is high enough that this really isn't a big problem. The prime number theorem says that the density of primes around N is roughtly 1/ln(N). So if you want to find a k-digit prime, you should expect to find one after k tries on average. (You can of course be clever and only consider odd numbers, and then you'll find one after k/2 tries on average). So Rabin-Miller takes O(k) time on k-bit numbers, and actually finding a prime takes O(k) tries on average. That's quite a good tradeoff actually.

I'm pretty certain this is how most modern crypto software generates RSA primes (guess and then check with Rabin-Miller). No, it's not super fast, but it's quite reasonable, and you usually only have to do it once.