This was brought up in an earlier thread, but it was thought to be confined to Red Hat. I have two Debian boot disks, and the ssh host keys were identical. For example, here's the ssh1 key:

/etc/ssh/ssh_host_key.pub:
1024 35 13246715431123624587068093985953739599556586251849
65646067039530185881027682926790107325829767851502
61172839583366348570501760986855833185198812904005
66450672384422407981371335146439765907427765458695
10826507932428488604746028665053148928531549762015
99459828391221129187969570520125283410016620603482
119346871 root@host1.linode.com

You can see that it was actually generated on host1.linode.com.

My advice would be not to trust any anonymous user's advice about security, but I replaced my keys (from the console, not an ssh login) with:

cd /etc/ssh
/etc/init.d/ssh stop
mkdir oldkeys
mv *_key* oldkeys
ssh-keygen -N "" -f ssh_host_key -t rsa1
ssh-keygen -N "" -f ssh_host_rsa_key -t rsa
ssh-keygen -N "" -f ssh_host_dsa_key -t dsa
/etc/init.d/ssh start

One could also try just replacing the keys and sending a HUP; that might (or might not) work without disrupting existing ssh sessions.

As noted in the Red Hat instructions, changing the host keys will cause ssh clients that have previously logged in to complain about altered keys.

This is going in the queue to be fixed ASAP. I'll update the Debian template distros. But for you guys using Debian, I suggest fixing your keys.

Thanks,
-Chris

Actually Debian provides a standard way to do this. Just skip "/etc/init.d/ssh stop" and do "/etc/init.d/ssh reload" instead of "/etc/init.d/ssh start".