Только купил себе сабж (virtual dedicated server), уже ssh во всю брутфорсят черти. Сижу думаю, чё поставить, чтобы прекратить это. Есть советы?

У мну тоже в логах ничего хорошего не увидишь... но с хорошим паролем на руте и остальных логинах еще ничего не происходило.... хотя данный вопрос тоже интересует.

Пароль поставить и не дёргаться :)
У меня несколько серверов есть, ко всем пытаются ssh-пароли подобрать. Равно как веб-сервера на всякие php-уязвимости сканируют, уже давно перестал на это внимание обращать. ssh пароли сейчас обычно бот-неты сканируют, соответственно, с кучи разных ip, поэтому динамически ip не забанишь. Обычно не больше десятка попыток (скорее не более 4-5) на логин, кроме рута.
Но, всё же, общие правила:
1) заблокировать доступ по ssh для логина root. Если нужно работать под рутом, логиниться обычным пользователем, и делать su.
2) создать группу ssh-allowed (условно), и разрешить ssh-доступ только на логины из этой группы. Желательно, "технические" логины вроде "web", "www", "mysql" и т.п. в эту группу не включать, не говоря уж про root.
пароли должны быть не очень простыми, но на самом деле, сканируют только самые примитивные. То есть, паранойи не нужно.

Убрал удалённый логин руту, поставил fail2ban, и теперь наблюдаю, как бот банит ботов.