QUOTE: Scripts that allow brute forcing of vulnerable keys (see this as rainbow tables for SSH keys) are in the wild so we would like to remind all of you to regenerate SSH keys ASAP. Please keep in mind that SSL certificates should be regenerated as well. This can be even more problematic if you had your certificates signed since you'll have to go through this process again (and possibly pay money again).
Update 2310 UTC: The new Debian package for SSH (ssh_4.3p2-9etch1) also applies a package called "openssh-blacklist". After this update, your SSH server will refuse keys from the compromised set. The package also installs a new tool called "ssh-vulnkey" that can help in hunting down key files that contain weak keys. Note that in combination with the existing ssh-keyscan, ssh-vulnkey can be used to easily identify servers that use weak host keys, so while these Debian patches help those who patch, they also make attacks easier against those who did not yet patch.
QUOTE: But the bug introduced by Debian effectively reduces the strength of the key to 32768 permutations, which is 16 bits. Famed security researcher HD Moore has actually already pre-calculated all of the potential keys for the most common cases. It took mere hours. So now you can be hacked even without someone brute-forcing your encryption