Copying from SANS Internet Storm Center diary:
Debian and Ubuntu Linux users should look into their OpenSSH setup. It turns out the used PRNG (Pseudo Random Number Generator) used was predictable.
Remember patching isn’t enough, you need to regenerate keys generated on these machines! Including those used in SSL certificates (X.509).
Worse: even good keys apparently can be exposed due to this. Quoting from the Debian reference below:
«Furthermore, all DSA keys ever used on affected Debian systems for signing or authentication purposes should be considered compromised; the Digital Signature Algorithm relies on a secret random value used during signature generation.«
So merely using your (good) keys on an affected machine might be enough to get the key itself compromised.