OpenSSLに欠陥があったようです

Memo Ubuntu

といってもオリジナルのOpenSSLではなく、Debian系実装のみの欠陥だそうな。

Debian GNU/Linuxで、0.9.8c-1以降のopensslパッケージに 欠陥が発覚し、修正版パッケージがリリースされた。なお、オリジナルのOpenSSLにこの欠陥はない。

Debianのopensslパッケージに欠陥発覚 | スラド セキュリティ

オープンソースソフトウェア、あるいは一部の商用ソフトウェアでも利用されている、OpenSSLという暗号化ライブラリに、Debian開発者の当てたパッチが原因で予測可能な乱数を生成してしまう脆弱性が入り込んでしまいました。暗号にとって乱数は非常に重要です。予測可能な乱数を使ってしまうと、それが暗号を破る手がかりとなってしまいます。ライブラリの脆弱性なので影響範囲も大きく、OpenSSH, OpenVPN, DNSSECの鍵やX.509証明書などが影響を受けます。特にOpenSSHは非常に大きな問題です。

http://blog.japan.zdnet.com/jla/a/2008/05/debian_ubuntuop.html

対処法に関してはDebian WikiのSSK Keysというページが詳しいです。
ちなみにおいらはSlicehostをUbuntuで動かしているので、OpenSSLとそれに関連するパッケージをインストールしなおしました。UbuntuのSecurity Noticeによると

The problem can be corrected by upgrading your system to the following package versions:
Ubuntu 7.04: libssl0.9.8 0.9.8c-4ubuntu0.3
Ubuntu 7.10: libssl0.9.8 0.9.8e-5ubuntu3.2
Ubuntu 8.04 LTS: libssl0.9.8 0.9.8g-4ubuntu3.1

USN-612-1: OpenSSL vulnerability | Ubuntu security notices

ということですので

~ > sudo aptitude update
~ > sudo aptitude install openssl
~ > rm /etc/ssh/ssh_host_*
~ > dpkg-reconfigure openssh-server
~ > rm -Rf ~/.ssh

とやっておきました。現状ほぼ放置している状態なので、OpenSSLで影響を受けるのはOpenSSHのみなので、これで大丈夫でしょう。あとはローカル側から再度キーを転送すればOKです。