Basically, someone decided to remove the random number generator from SSL and SSH key generation because it caused 2 other packages to warn.
So, the only entropy is the process ID.
Host keys are generated within the first 200 processes.
New-system SSL keys are usually within the first thousand.
Max PID for DebIan is 32768.
It took 2 hours to generate all of the possible 1024-bit keys.
It took 6 hours to generate all of the possible 2048-bit keys.
Pre-computed private keys for all 4k and smaller keys are downloadable.
ie, all DebIan private keys should be regenerated somewhere safe.
This could affect AIX, Solaris, or anywhere else that someone has copied their home key to.
You have to believe that, by now, someone out there is brute forcing distributely across the entire internet, looking for these keys.