If you are absolutely sure that they gained root access then there is no other alternative then to kill the internet on those machines.
And then you should back up all the data you want to preserve so that you can reinstall those machines safely. There is no telling if they installed another SSH server or other nasty things like rootkits.
Most attackers install their own SSH server so that any changes your make to patch your security holes aren't putting them out of business.
Unless you have aide installed and made regular checksums of all the files and configs then you have no idea if anything is changed since the attack.
You can also try rkhunter and chkrootkit to find any rootkits on your system, but they aren't conclusive.
The only way to be sure that you are in the clear is a total new start on all the affected machines.
PS: We all got it now, fail2ban is a great tool ;-)
--
Met vriendelijke groet,
Kees de Jong
De informatie opgenomen in dit bericht kan vertrouwelijk zijn en is uitsluitend bestemd voor de geadresseerde(n).
Indien u dit bericht onterecht ontvangt, wordt u verzocht de inhoud
niet te gebruiken en de afzender direct te informeren door het bericht
te retourneren.
--
The information contained in this message may be confidential and is intended to be exclusively for the addressee(s).
Should you receive this message unintentionally, please do not use the
contents herein and notify the sender immediately by return e-mail.