A weakness has been discovered in implementation of OpenSSL that Debian and Ubuntu provide. This random number generator has been shown to be predictable in certain ways. Consequently, encryption keys generated by OpenSSL, including SSH host keys and SSH public/private keypairs, should be considered compromised. (Upgrading to the latest version of openssl in Debian and Ubuntu will offer to regenerate your host keys.)
What is interesting is how this vulnerability was created in the first place. In order to create keys, OpenSSL acquires randomness from a bunch of sources and adds it to a buffer created in uninitialized memory.
Valgrind (a debugging/profiling tool) detects, among others, situations where programs do computations based on the results of uninitialized memory. These are almost certainly bugs. Except when the express goal of your program is to produce something random.
A Debian developer added the following patch to OpenSSL,
+ /* Keep valgrind happy */ + memset(tmpbuf, 0, sizeof tmpbuf); +
thereby replacing perfectly good semi-random data with zeroes. As it turns out, this is enough to greatly reduce the key search space for attackers.
Diagnostics (and compiler warnings, and the like) can be dangerous when interpreted by amateurs.