This is worth reading.
Update: The Debian people created a website with instructions to rollover keys. And there’s also a Perl script for testing SSH servers an other packages for vulnerabilities.
Update 2: Bruce Schneier jumped in. And here is a xkcd cartoon and some source.
Update 3: Here are some useful tips (in German).
