This is an extension of Bill's comment.
It is certainly reasonable to use strong probabilistic tests and then verify with the AKS algorithm. In fact, if we look for primes alternately above and below the target number and test with AKS, where each primality test takes time at most $\log^{O(1)}N$, and there is an approximately $\dfrac{1}{\log N}$ chance that each is prime, one would be at least 99% sure to find a prime in time $O(\log^{O(1)}N)$. But this is not deterministic - conceivably, there exists an interval where this works very poorly, far worse than logarithmic time. To be fair, I suspect such an interval does not exist in the numbers up to $2^{64}$. But speaking generally, a deterministic algorithm might be desired.
To that end, I refer you to the results of Polymath4 "Finding Primes," a collaborative mathematical experience that sought to find a method to deterministically find primes of about a given size. In their paper, they describe deterministic methods that take time $O(N^{.5 + \epsilon})$, which I think is pretty exciting.
Ultimately, I would say that Bill's suggestion of probabilistically checking numbers and then verifying their primality is optimal. But the promise of a deterministic algorithm is... quite alluring, I think, too.