A mi se me hace que los caballitos que te pusieron informan al que los puso cuando cambias el password de root... Cosas que debes checar es si hay algun usuario nuevo creado, y tambien ver los servicios que corren... Y no estaria de mas que te pongas un sniffer y cambies el password de root para ver si pasa algo por ahi....
Lo que yo haria es reinstalar la distro... Aunque esto puede no ser lo mejor, para mi el saber que alguien ya le puso mano, seria dificil el no temer que tenga algo muy oculto.. En los scripts que hallaste en /tmp quizas vengan comentarios y coasas asi que te pueden servir a hacer una busqueda en google para hallarle remedio... De seguro a alguien mas le pegaron... La mejor prevencion definitivamente es tener la maquina siempre actualizada, y tambien endurecida... Con bastille o algo asi... No permitir por ejemplo que root pueda hacer login por ssh, sino que tenga que ser un usuario y este usar sudo o su, que se registra en los logs.... Bueno, no soy experto en seguridad... Te paso nomas mis impresiones.
