Как бороться (найти и уничтожить) с руткитом на Linux-сервере (в моём случае, Ubuntu Server)?
Переставить систему с нуля. Это наиболее правильно для сервера.
Я делаю в таком случае миграцию данных на промежуточный сервер, реинсталл текущего и миграцию обратно. Ну или просто на другой чистый сервер.

Линукс — сложная система. Каждый сисадмин желает знать где сидит руткит. Но таких мест слишком много. Что то упустил и весь многодневный труд на смарку. В перспективе реинсталл проще.