Eu tomei várias providências para proteger meus servidores:
O primeiro é o óbvio:
Não execute ssh em uma porta padrão para se livrar dos ataques habituais de skript kiddies.
O segundo também é state-of-art:
Use um daemon de ataque. Um daemon de detecção primeiro espera uma sequência de ocorrências em portas e protocolos específicos antes de abrir a porta para a conexão ssh no servidor. Assim, o servidor ssh é invisível para qualquer atacante até que ele atinja a seqüência de portas correta com um cliente de interceptação. A maioria das implementações do daemon - da - da - da - da - na fornecem um mecanismo para integrar as seqüências transacionais, de modo que a sequência de batida é alterada após cada login bem-sucedido.
Com esta configuração padrão, você recebe um pouco mais de uma camada de segurança.
Usar nomes de usuário e senhas criptografados e restringir o ssh-login a um usuário específico (não-root) também é recomendado. Você pode alternar para o usuário root no servidor ao executar tarefas raiz.
Instalar um sistema de monitoramento como o nagios também fornece mais segurança para você e seu ambiente, é fácil de configurar e também é fornecido através do sistema de empacotamento do ubuntu. Você pode configurá-lo para enviar e-mails quando alguém estiver fazendo login no seu servidor via ssh, então pelo menos você obterá as informações necessárias para fazer outras investigações.
Mas, para ser honesto: se alguém acessou seu servidor como root, você deve fazer uma reinstalação completa de tudo. Poderia haver substituições de binários que não são fáceis de detectar, introduzindo backdoors. Imagine que você execute um comando simples como useradd e os binários foram substituídos, de modo que, ao executar o comando, uma conexão tcp seja aberta e as credenciais do usuário sejam enviadas para o intruso. Ou pior: o binário ssh-server foi substituído por uma versão personalizada que permite o acesso através de uma combinação de usuário-senha.