Apparently the source of randomness in OpenSSH's implementation was raising a warning in a code checker. This caused some concern in Debian for some reason, but the solution was simple:
Remove the code that seeded the random number generator.[1]
Making all keys generated on Debian and Debian-based distros (like, say, Ubuntu) easily guessable.
Sort of like the keys I've been using to access the shell account in Dreamhost. (I've deleted them from .ssh/authorized_keys, so don't bother trying.)
So now I get to regenerate the keys on both my Ubuntu machines, as well as delete the .ssh/known_hosts entries on half a dozen machines.
Sigh.
[1] Supposedly. I can't find a good writeup on exactly what happened to cause the PRNG to not seed properly, as the line they removed shouldn't have been the only source of entropy while seeding the PRNG. But whatever they did, they made the keys insecure, and now I have to regenerate all of them.