A melhor prática é executar o ssh em uma porta diferente da porta 22 para começar. Você pode mudar isso em /etc/ssh/sshd_config
alterando o valor para Port 22
.
Se você, por exemplo, executar o ssh na porta 8822, abra essa porta no seu firewall (e no host linux se você estiver executando um firewall lá), você deve poder se conectar usando ssh <your_user>@<your_public_ip> -p 8822
. Isso é claro, se o seu provedor não está bloqueando as portas.
Editar:
Além disso, você pode querer começar a autenticação pki definindo PermitRootLogin prohibit-password
em /etc/ssh/sshd_config
. Além disso, você deve usar senhas / frases longas e razoavelmente complexas.
(Como sugerido pela telcoM)