Before a ssh host to accept a ssh client request, the host have to be installed with SSH host key. Usually if you are installing the ssh servers (which usually come as default package in most Linux distro) from a package (e.g. rpm or deb), the installation script will take care the ssh host key generation for you.
However, in any cases you removed the ssh host key (usually sit under /etc/ssh/), you will no longer be able to get into the machine via ssh until the host key is generated.
So this is what you get when your ssh host is gone.
$ ssh firstname.lastname@example.org
Connection closed by x.x.x.x
And if you have a console access to your machine, you will be seeing something like this on /var/log/auth.log (or /var/log/messages ... depends on your syslog configuration).
Jan 17 07:42:38 localhost sshd: error: Could not load host key: /etc/ssh/ssh_host_rsa_key
Jan 17 07:42:38 localhost sshd: error: Could not load host key: /etc/ssh/ssh_host_dsa_key
Jan 17 07:42:38 localhost sshd: error: Could not load host key: /etc/ssh/ssh_host_ecdsa_key
Jan 17 07:42:38 localhost sshd: fatal: No supported key exchange algorithms [preauth]
In order to fix this, ssh host key have to be regenerated
ssh-keygen -t rsa1 -f /etc/ssh/ssh_host_rsa_key -N ‘’
ssh-keygen -t dsa -f /etc/ssh/ssh_host_dsa_key -N ‘’
ssh-keygen -t ecdsa -f /etc/ssh/ssh_host_ecdsa_key -N ‘’
The option -N refers to the new passphrase to be used. In above example '' means empty. Should you want a passphrase be assigned to the key, you may want to put it like -N 'your_pass_phrase'