If I want a 128-bit security level, I'm willing for a random guess of my key to have a 2^-128 chance of being correct. I'm likewise willing for a prime I generate to have a 2^-128/uses chance of not being prime (where uses is equal to the number of times I'll actually be using it).
I can't be 100% certain that a large number is actually prime. But I can be certain enough. Having a 2^-80 chance of being wrong isn't good enough when I want a 2^-128 security level.
You can't compare these 2 scenarios directly, because in practice:
- attackers can take as many guesses as they want against a piece of data protected by a 128-bit key, but
- attackers get only 1 chance that a particular piece of data protected by a supposed prime is not a prime.