Si realmente se os ha colado alguien, basicamente pueden darse 2 posibilidades.
1º Que quien haya entrado, haya conseguido el password para la cuenta de root a puro huevo, o bien a base de brute force si esto era posible tal como estaba configurado el servidor.
2º Que haya conseguido entrar aprovechando algun fallo de seguridad en algun servicio, exploit etc.
En cualquier caso sigue habiendo otras dos posibilidades, que despues de entrar simplemente se haya apuntado el pass de administrador conseguido de una forma u otra, o que os haya metido un rootkit para borrar sus huellas y volver a entrar cuando quiera.
Si simplemente tiene el pass de administador o se ha hecho de alguna cuenta con privilegios para poder configurar el servidor y arrancarlo, entonces lo teneis muy facil, es cambiar el pass de root y borrar las cuentas que no debeieran estar ahí.
Si os ha metido un rootkit, normalmente el rootkit habra sobreescrito programas como el ls, ps, users, who etc , lo que tienes que hacer es copiar el ls de la distribucion a un directorio cualquiera, y luego asegurandote de que usas el ls de la distribucion, usarlo para comparar los tamaños de los archivos que se suelen sustituir con los rootkits, si veis que los tamaños no difieren, se puede pensar con "cierta seguridad" que no han colado un rootkit y solo es cuestion de que han conseguido un pass.
Un saludo.
P.D.
Tambien hay sistemas automaticos para comprobar esto, como chkrootkit etc, lo que ocurre, es que a sistema automatico para encontrar algo... sistema automatico para evitar que lo encuentre.