FC4 - Years out of date. There's no question how they got in, the system was out of date, or let go. That's like saying "Oh, I'm running redhat 7.3, but I'm just going to let it go".

Every couple of years you need to have your system replaced and updated. When you do so, you should update the OS as well (ie: fc4 to fc8 now, etc). Hardware (even server hardware) degrades over time, and needs to be replaced. It happens, like I said, every couple years or so, you should be upgrading for better performance.

John (aka JTR) is a password cracking system. So, not only have you been hacked, but your passwords have been compromised. Not just ONE password, but ALL of them are gone. You'd best mail your users or it will happen again!

While you're at it, require ssh keys to login to the server, NOT just as root, but as any user. This will help solve issues.

Mod_security is iffy, you're going to have problems there. Best result is use something like suhosin that doesn't go out of it's way to break functionality, yet provides at least a bit of security.