ssh server unreachable because of weak openssl host key

I had a strange problem lately with weak Debian openssl keys. When I upgraded openssh-server host keys regerated, but since they are depended on host data, generated key is always the same and ssh server blacklists them making host unreachable via ssh.

If you get output similar to this, you are in trouble:

root@black:~# dpkg-reconfigure openssh-server
Creating SSH2 RSA key; this may take some time ...
Creating SSH2 DSA key; this may take some time ...
Host key 9d:83:3a:62:25:0d:c4:e9:81:b0:5a:de:47:3e:b0:e7 blacklisted (see ssh-vulnkey(1))
Host key 27:cc:9a:f2:e3:be:0d:44:94:fa:86:60:36:dc:04:2e blacklisted (see ssh-vulnkey(1))
Restarting OpenBSD Secure Shell server: sshdHost key 9d:83:3a:62:25:0d:c4:e9:81:b0:5a:de:47:3e:b0:e7 blacklisted (see ssh-vulnkey(1))
Host key 27:cc:9a:f2:e3:be:0d:44:94:fa:86:60:36:dc:04:2e blacklisted (see ssh-vulnkey(1))

First step was to install dropbear (which comes in dropbear Debian package) and change port in /etc/default/dropbear to something other than 22:

# change to NO_START=0 to enable Dropbear
NO_START=0

# the TCP port that Dropbear listens on
DROPBEAR_PORT=1022

This will allow us to connect using ssh -p 1022 black if something goes wrong (and from my expirience it will).

Then, generate rsa and dsa keys on some other host using:

dpavlin@tab:/tmp/black$ ssh-keygen -t rsa -f ssh_host_rsa_key -C black
Generating public/private rsa key pair.
Enter passphrase (empty for no passphrase): 
Enter same passphrase again: 
Your identification has been saved in ssh_host_rsa_key.
Your public key has been saved in ssh_host_rsa_key.pub.
...
dpavlin@tab:/tmp/black$ ssh-keygen -t dsa -f ssh_host_dsa_key -C black
Generating public/private dsa key pair.
Enter passphrase (empty for no passphrase): 
Enter same passphrase again: 
Your identification has been saved in ssh_host_dsa_key.
Your public key has been saved in ssh_host_dsa_key.pub.

and copy them over using dropbear which still works:

dpavlin@tab:/tmp/black$ scp -P 1022 ssh_host_* root@black:/etc/ssh/

now restart openssh-server with

root@black:~# /etc/init.d/ssh restart
Restarting OpenBSD Secure Shell server: sshd.

and you can test your normal ssh connection to port 22 and remove dropbear server.