General

As a follow-up to the previous post, it has now been confirmed that there is an SSHD rootkit in the wild that spreads itself if you ssh from an infected server to another. The details are explained in this article as a summary of the webhostingtalk thread:
http://isc.sans.edu/diary/SSHD+rootkit+in+the+wild/15229
Unfortunately, cPanel is a victim of this malware and their workstation(s) have been infected leading to possible infection of client servers:

Salutations,
You are receiving this email because you have opened a ticket with our support staff in the last 6 months. cPanel, Inc. has discovered that one of the servers we utilize in the technical support department has been compromised. While we do not know if your machine is affected, you should change your root level password if you are not already using ssh keys. If you are using an unprivileged account with “sudo” or “su” for root logins, we recommend you change the account password. Even if you are using ssh keys we still recommend rotating keys on a regular basis.
As we do not know the exact nature of this compromise we are asking for customers to take immediate action on their own servers. cPanel's security team is continuing to investigate the nature of this security issue.
–cPanel Security Team

We would recommend (as we do on our helpdesk) that you change your root passwords immediately after any third-party has accessed your server. Additionally, to those affected, please remember that you cannot “clean” this infection, you must reinstall your OS and restore user accounts from backups.

There's a quickly spreading root compromise that everyone should check for that latches onto the sshd daemon. See the following threads for details on detecting the compromise:
http://forums.cpanel.net/f185/sshd-rootkit-323962.html
http://www.webhostingtalk.com/showthread.php?t=1235797
At the very least check for the existense of libkeyutils.so.1.9
As with all root compromises, simply deleting it and carrying on is not an option. If your server has been compromised you most likely cannot trust it and will need to perform an OS reinstall and restore from backups. However, unless you fix the original method of compromise, the server may simply be exploited again.
On a maybe related note, though not proven, it appears that there's a scary kernel exploit about which RedHat should have fixed soon (CentOS and CloudLinux are likely to follow quickly afterwards). So, make sure that your kernel is kept up to date at all times and look out for a new one soon:
https://access.redhat.com/security/cve/CVE-2013-0871