Não há uma maneira completamente segura de garantir que o servidor esteja limpo. Mas há algumas abordagens que você pode adotar para reduzir o risco.
Você pode reinstalar o servidor. Se você sabe o que está fazendo, é possível reinstalar um servidor remotamente. Um compromisso que sobrevive a uma reinstalação é muito mais difícil de ser executado do que apenas instalar um rootkit praticamente invisível. Então, se você realizar essa reinstalação, suas chances melhorarão.
Obviamente, a reinstalação precisa ser executada usando uma mídia de instalação limpa. Eu usaria scp para copiar a imagem para o servidor. Se você não conseguir se conectar ao servidor usando ssh, você terá dificuldades.
Compare a chave do host ssh no servidor com a chave pública que você vê para o servidor. Algumas classes de ataques mitm sistemáticos podem ser reveladas dessa maneira.
Substitua a chave do host ssh por uma que você gerou (no caso de alguém ter uma cópia da que estava no servidor quando você a obteve).
Use logins baseados em chave. Se a chave secreta vazar, ou se você tiver a chave pública errada em seus hosts conhecidos, os ataques mitm seriam possíveis. Mas alguns dos ataques mitm que seriam possíveis com isso só funcionam contra logins baseados em senha e não contra logins baseados em chaves.
Se o servidor tiver algum tipo de hardware de computação confiável, você poderá usá-lo para verificar a integridade do sistema operacional instalado. Mas isso, obviamente, não pode lhe dar proteção total contra cenários em que o próprio hardware está comprometido.
Coisas a serem observadas incluem a possibilidade de alguém ter acesso ao servidor pelo console, bem como a possibilidade de que alguns dos caminhos de comunicação dentro do servidor tenham sido grampeados (por exemplo, um dispositivo que espiona passivamente as comunicações SATA e Injetar ativamente dados durante a inicialização seria viável para um adversário bem financiado, e seria praticamente impossível verificar remotamente.)
Observe também que, se você estiver executando em um servidor virtual, o servidor host terá acesso total ao armazenamento e à memória. Não há nada que você possa fazer para proteger seu servidor virtual se o servidor físico no qual ele está hospedado estiver comprometido.
Mantenha as partes mais sensíveis dos seus dados longe de servidores nos quais você não confia. Isso pode significar que você tenha que depender dos servidores que você possui em outros locais para determinadas tarefas. Por exemplo, para a validação de senha, você provavelmente pode tolerar a lentidão que seria causada por não permitir que o próprio servidor veja as senhas e adiar a validação para um servidor em um local confiável.