Заменить пароль root'а и никому никогда ни под каким предлогом его не давать. Система является абсолютно надежной, если суперюзер один. Если все же людям нужно исполнять какие-то конкретные команды от root'а, то тебе может помочь команда sudo.
Вариагт с ssh пажалуй самы прикольный, а обычный телнет просто прикрой, тем более что через ssh можно напрямую рутом заходить без опасения что снифернут :) проверенно ( в том числе и сниффингом)