Generating the keys for the RSA cryptosystem in probabilistic polynomial time
Short version: All the cool kids are using Randomized Algorithm ! 

Boring version:


Any deterministic (part of a) crypto system can be broken !  [Goldwasser Micali]
Primes density is pretty high (higher than one intuitively expects) as we talk of big numbers. Prime No. Theorem : #of primes between $1$ and $x$, $\pi(x) = \frac{x}{ln(x)}$ , So if randomly picking no.s usually means you have a fairly high chance of getting a prime.. :)
Primality checking with Rabin Miller (probabilistic) is way faster than AKS (deterministic)