This would sound like there is a modified SSH binary set on your server, I would suggest running rkhunter and/or chkrootkit if there are any backdoors installed, if any are found I would suggest reading up on them and cleaning them up.
Also check your root accounts history to see what is happened, if the attacker left any traces.
You can also reinstall the SSH package ( or any other package that would be exploited )trough your package manager ( rpm/apt-get or any third package manager ) that would replace the binaries with the default binaries, rerun the rkhunter and see if there are still any matches.
And lastly, you could do a check which packages have the files modified, an example for RPM based systems:
Following command would list any changes to the RPM packages:
rpm -qa | xargs rpm --verify --nomtime | less
If the verification fails, it would show you which part did fail:
c %config configuration file
d %doc documentation file
g %ghost file (i.e. the file contents are not included in the package payload).
l %license license file.
r %readme readme file.
S file Size differs
M Mode differs (includes permissions and file type)
5 MD5 sum differs
D Device major/minor number mismatch
L readLink(2) path mismatch
U User ownership differs
G Group ownership differs
T mTime differs
Above is from the RPM manual - http://www.rpm.org/max-rpm/s1-rpm-verify-output.html
Another solution, would be to backup your data and reinstall the system when time allows, as it seems that you are in a tight spot right now.