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.