É provável que seja um problema de firewall, posso me conectar bem aqui (ele me pede uma senha).
Por favor, não use sudo ssh , apenas ssh está bem. Além disso, desative a autenticação baseada em senha e use a autenticação baseada em chave, se possível.
Para diagnosticar problemas, execute ssh com a opção -v ( -vvv para máxima verbosidade):
ssh -vvv user@host