“If they got unlucky and started testing for primes at the beginning of a huge gap, the algorithm would take a very long time to run.”
Wouldn't it also mean that the first prime after such gaps will be selected more often, assuming a random starting point for prime searches? That might be a bigger problem than having to wait longer for the selection to finish.
Honestly, I wouldn't worry about either problem. The degree of "unlucky" required here is almost certainly below the noise threshold. Otherwise we would have noticed by now, because prime-based crypto is, after all, not a theoretical thing, but something extremely-widely deployed in the field, and in practice, we do not observe this problem. Since we do not observe this problem, we therefore are not observing this problem; QED.
(The "noise threshold" is provided by the fact that processors are not in fact 100% accurate, but do indeed have a low-but-non-zero error rate. When the probability of a randomized algorithm failing drops below the probability that the processor literally got the computation wrong, it ceases to matter in practice. And one could argue it ceases to matter even before that, but it certainly ceases to matter at that point. Hence I call it the "noise floor". It's so low we are used to just assuming it is zero, but in fact it is not.)
This is the kind of work that the NSA, had they known it decades ago, would have kept to themselves. They certainly have no shortage of mathematical talent working on the problem.
Wouldn't it also mean that the first prime after such gaps will be selected more often, assuming a random starting point for prime searches? That might be a bigger problem than having to wait longer for the selection to finish.