Lets face it, passwords are useless. Every day you hear about some random hacker pop'ing a major company and then posting the database that contains the users login and passwords.
In some cases, the passwords are hashed, often they are not. So how can you help from being a part of the problem? Multi-factor authentication is one way to help.
If you have never heard of this before, check out the following link [wikipedia]. However the problem with setting up two factor on your server is that:
A.) It costs a bunch
B.) It's kind of hard if you have never done it before
Enter google authenticator. For a while now, google has allowed you to use a token to login to your google accounts, and they were kind enough to release the API as well.
[google authenticator]
So how do you get this protection on your server? Pretty easy actually. Lets assume you are working on a fresh install.

yum install pam-devel git make gcc gcc-c++ kernel-devel 

git clone https://code.google.com/p/google-authenticator/

cd google-authenticator/libpam/
make
make install

Now to configure this just enter:

vi /etc/pam.d/sshd
...in the 2nd line enter:

auth required pam_google_authenticator.so

Then update SSHD

vi /etc/ssh/sshd_config
... set the following values

ChallengeResponseAuthentication yes
UsePAM yes

Then just type service sshd restart
Now enter the user you want to use this with (You are not seriously going to use root right?!)

su username
google-authenticator

...Read and answer (this is one way)...

Do you want me to update your "~/.google_authenticator" file (y/n) <strong>y</strong>

Do you want to disallow multiple uses of the same authentication
token? This restricts you to one login about every 30s, but it increases
your chances to notice or even prevent man-in-the-middle attacks (y/n) <strong>y</strong>

By default, tokens are good for 30 seconds and in order to compensate for
possible time-skew between the client and the server, we allow an extra
token before and after the current time. If you experience problems with poor
time synchronization, you can increase the window from its default
size of 1:30min to about 4min. Do you want to do so (y/n) <strong>n</strong>

If the computer that you are logging into isn't hardened against brute-force
login attempts, you can enable rate-limiting for the authentication module.
By default, this limits attackers to no more than 3 login attempts every 30s.
Do you want to enable rate-limiting (y/n) <strong>y</strong>

When you first start it will give you a URL and some codes, simple copy the URL to your browser and scan the QR code with google authenticator (Android app store or Apple iTunes free download) and boom your good to go.
Before you logout, TEST this by staying in that user account and using ssh localhost
It should ask for "Verification code: " that is what you see on screen.
Hopefully this is helpful, let others know below if this worked for you.

Notes!

The only downside to this is that doing so does not allow you to use public key authentication at the same time.
I've actually had issues when trying to do this with a root account, so try to do it with a normal account first.