ssh_exchange_identification: Connection closed by remote host - this was the message returned when trying to connect to a server (Debian, exposed to Internet, using a non-standard port for ssh service) using a valid key. After 5+ retries i finally managed to connect.

I checked the "/var/log/auth.log" logs and the enemy showed up: someone was brute-forcing the root access spawning many connections simultaneously (and i guess this was the reason i could not complete the ssh connection)

The fix: fail2ban !
[cc lang='bash']
\$ apt-get install fail2ban -y
# disable default jails
\$ sed -i 's/\^enabled = true\$/enabled = false/g' /etc/fail2ban/jail.conf
# create custom ssh jail using standard sshd filter
\$ cat \<\<'EOF' > /etc/fail2ban/jail.local
[ssh]
enabled = true
port = 22222
filter = sshd
backend = polling
logpath = /var/log/auth.log
maxretry = 5
bantime = 3600
EOF
\$ /etc/init.d/fail2ban restart

\$ fail2ban-client status ssh
\$ iptables -L -nv
\$ tail /var/log/fail2ban.log
[/cc]