Bien, analizando lo que comentas, primero de todo, es recomendable el ssh porque es mas seguro que hacerlo sin encriptar.
Segundo, yo usaria un software para buscar vulnerabiliades en tu server como GFI o Retina, y asi verificas que no tengas ningun agujero de seguridad.
Lo de la LIVECD, me referia a que cambies siempre las contraseñas desde un ordenador que sepas ha ciencia cierta que es 100% seguro. No sabes si han sacado las claves a traves de ti o de tu equipo , sin que lo hayas percibido.