The Code you Input:
sudo dpkg -i openssh-server_6.6p1-2ubuntu1_amd64.deb
Should install the OpenSSH-Server and not Remove it. Anyway, If you want to install it the Correct way, Open Up a Terminal Using Ctrl+Alt+T and Type:
sudo apt-get install openssh-server
and it will install The OpenSSH-Server, and if it already Installed, It Will Update it and if it's up to date then nothing will be done, Also, If You have trouble with the Command Above Try:
sudo apt-get update
And As listed above, Ubuntu Upgrade OpenSSH-Server to an Older Version than the Latest, So To Install the Latest, First we need to remove any existing old OpenSSH-Server, Bring up a Command Prompt Using Ctrl+Alt+T and Type the Following, Pressing Enter after Each Line:
sudo apt-get remove openssh-server
and Then to Install the latest
wget http://mirror.aarnet.edu.au/pub/OpenBSD/OpenSSH/portable/openssh-6.6p1.tar.gz
tar -xvf openssh-6.6p1.tar.gz
cd openssh-6.6p1
./configure --prefix=/usr --sysconfdir=/etc/ssh
--with-md5-passwords --with-privsep-path=/var/lib/sshd
sudo make install
And you should now Have OpenSSH-Server 6.6 P1, To Check, Type in a Terminal:
sshd -V
Your original host keys would be deleted if you had purged openssh-server, using either apt-get purge openssh-server or apt-get remove --purge openssh-server. In this case the keys would be regenerated, and would naturally be different. If openssh-server was just removed, the key files should not have been touched on reinstallation.
The host keys do indeed only depend upon the files in /etc/ssh/, unless ssh is configured to look elsewhere. This would be evident by any unusual looking HostKey lines in /etc/ssh/sshd_config. The default HostKey lines are:
# HostKeys for protocol version 2
HostKey /etc/ssh/ssh_host_rsa_key
HostKey /etc/ssh/ssh_host_dsa_key
HostKey /etc/ssh/ssh_host_ecdsa_key
HostKey /etc/ssh/ssh_host_ed25519_key
It is definitely worth checking the file to see whether you're using host keys from a non-standard location, as your key files appear not to have been modified.
If the keys on the server are as expected, the warning is most likely being generated at the client end of things. As Germar said, the problem could be caused by reuse of a dynamically assigned IP address which had previously been used by another server.
Best Answer
Open the terminal and type:
If that doesn't work, open the Ubuntu Software Center and browse to Edit -> Software Sources -> Ubuntu Software tab, and make sure that you have at least the main, universe and multiverse repositories marked with a check mark.