Coisas a verificar:
-
Verifique sua rota; em sua execução do cliente
traceroute <ip>
-
Verifique a resolução do seu nome; no seu cliente e servidor execute
dig <hostname>
-
Verifique seu firewall; em seu servidor execute
iptables --list
(teste ssh com seu firewall cliente desativado também) -
Reinicie o serviço;
/etc/init.d/sshd restart
(ou o que for apropriado para sua distro)
Além dessas questões, pode haver mais algumas, incluindo erros ou interrupções no provedor de VPS.