Login as the root and type the following command:

# /bin/rm /etc/ssh/ssh_host_*

Step # 2: Reconfigure OpenSSH Server

Now create a new set of keys, enter:

# dpkg-reconfigure openssh-server

Sample output:

Creating SSH2 RSA key; this may take some time ...
Creating SSH2 DSA key; this may take some time ...
Restarting OpenBSD Secure Shell server: sshd.