1) Delete your bad keys:
.ssh/id_*. Fix all systems where you're trusting those keys (think .ssh/authorized_keys); someone has already published a table of all private keys, so it's just a matter of time before your system is brute-forced.2) Update your systems. I see an "openssl-blacklist" package show up on both my Debian stable and my Ubuntu whateverletterthey'reon one. You'll get some debconf prompts about it clobbering stuff, including potentially your host keys, which means the next time you connect to the machine you'll get the "host keys have changed" message.
3) To make yourself feel less anxious, try running
ssh-vulnkey to print an analysis of keys in standard paths on your system. (Run it as sudo ssh-vulnkey -a to check all users on your system.) 