Enquanto estiver no servidor, verifique se o sshd está realmente em execução e está escutando na porta 22:
$ sudo netstat -anp | grep sshd
tcp 0 0 0.0.0.0:22 0.0.0.0:* LISTEN 1538/sshd
tcp6 0 0 :::22 :::* LISTEN 1538/sshd
Se você não obtiver resultados, ou eles não mostrarem que você está ouvindo no tcp 0.0.0.0:22 ... conserte isso.
Se você mostrar que o sshd está em execução e está escutando na porta tcp 22, verifique se não há nenhuma regra de firewall atrapalhando. Mais uma vez, no servidor:
$ sudo iptables -L | grep ssh
DROP tcp -- anywhere anywhere tcp dpt:ssh
Ou alternadamente,
$ sudo ufw verbose
Status: active
To Action From
-- ------ ----
22 DENY Anywhere
22/tcp DENY Anywhere
Se você vir uma regra como uma das opções acima, será necessário corrigir isso.
Se você não vir nenhuma regra de firewall no caminho e vir o serviço em execução no servidor, é hora de verificar sua estação de trabalho e a rede à qual está conectada. Você consegue se conectar a outros servidores? Você pode fazer ping na sua própria interface ou endereço de loopback? Etc.