After the recent disaster with Debian generated keys and other cryptographic random numbers, it seems that starting from even one day before the announcement of DSA 1571-1, botnets were already starting to bruteforce all 65'536 possible SSH keys which were produced by the vulnerable ssh-keygen package.
This proves the urgency for all administrators to replace their SSH keys immediately, not only the host keys, but also the keys of all users.