[wplug] OpenSSH on Debian -- generate new host keys?

[Will Rodina]

Hi everyone. Long time listener, first time caller.

Until recently, I was rather smug with the knowledge that my personal
ssh keys -- even the ones on my Debian boxes -- were not generated
using Debian's vulnerable ssh-keygen app. Then a couple days after all
heck broke loose, a friend of mine told me that my shell account on
his server came up with a couple positives when he ran ssh-vulnkey.

Ah, the sshd host keys. Never thought of those.

It now occurs to me that I actually have no idea how in the fleeping
fark to generate new host keys. It's always been done for me either
when doing a new install, or installing OpenSSH. I tried just removing
the Evil keys and restarting sshd, thinking it might complain that the
host keys were missing and prompt me to generate new ones... but it
just happily restarted. Ssh'ing into the box didn't give any host key
warnings at all, so I have to assume that they may be cached somewhere
else, too?

Can someone point me to something I can read that will tell me how to
beat down the old host keys and replace them with good ones? I assume
it involves ssh-keygen, but I'm not sure what other voodoo has to be
included to make it all come together.

Thanks.