An RPM Verify checksum mismatch (what you describe above) is certainly suspicious. Combined with logs from the "victim" server showing that your machine has been doing something nasty I'm left with three possibilities:
One of your users is being a nuisance.
Solution: Find the user, revoke their account, then pay them a visit and beat them sensible.
Some ancillary program has been compromised (e.g. CGI/PHP code on your web server) and is allowing outside attackers to execute arbitrary code.
Solution: Review your Apache and/or script logs to see if anything funky is happening. Close the hole.
Your box has been rooted (and a backdoor'd suexec installed).
Solution: Visit this question and several others that talk about post-mortem procedures. Rebuild the machine.
If you can't explain why suexec's checksum doesn't match what RPM thinks it should be, paranoia dictates wiping the machine and reinstalling from a known-good set of install media. This is especially true if your RPM checksum "always matched before"...
Note that it isn't necessary for your machine to have been rooted in order for someone to be launching SSH attacks from it (running the
ssh client binary doesn't require any special privileges beyond being able to open a network socket and talk to a remote host on port 22 -- Most machines allow this).
As a result your logs might not show anything, especially if the attacker gained access, sat on their hands for a while (until evidence of their breach rotated out of your log system) and then started launching attacks from your box.
Network traffic logs (netflow data, etc.) may show "unusual" traffic patterns - e.g. a large number of "flows", "connections", or a high packets-per-second rate with relatively low traffic (bits-per-second), but you would need a reliable external monitor (router/firewall, your ISP, etc.) to provide that data for it to be forensically useful.