Delayed login starting to get very annoying.

Here's the problem... when anyone goes to ssh into our machine 'choplifter' when the password is asked, it takes a good time for it to actually arrive at the prompt.

Now before you think you know what it is... here is what I've already checked.
-Since we run radmind, I checked to see with another server that was working fine, the sshd_conf was the same as the offending server. So no cipher problems.
-DNS and reverse DNS are working fine
-We use PAM for our kerberos5 login, I checked the .so files for both servers and they are the same
-straced the daemon, but all it shows is:
Aug 4 14:28:29 choplifter sshd(pam_unix)[21163]: check pass; user unknown
Aug 4 14:28:43 choplifter sshd[21163]: pam_krb5: authentication succeeds for `test'
Aug 4 14:28:43 choplifter sshd[21163]: pam_krb5: pam_sm_authenticate returning 0 (Success)
Aug 4 14:28:47 choplifter pam_pts[21163]: service granted to test
Aug 4 14:28:47 choplifter sshd[21163]: Accepted password for test from 141.213.231.202 ssh2
Aug 4 14:28:47 choplifter sshd[29908]: lastlog_perform_login: Couldn't stat /var/log/lastlog: No such file or directory
Aug 4 14:28:47 choplifter sshd[29908]: lastlog_openseek: /var/log/lastlog is not a file or directory!
Aug 4 14:28:47 choplifter sshd(pam_unix)[29908]: session opened for user test
Aug 4 14:28:47 choplifter sshd[21163]: lastlog_perform_login: Couldn't stat /var/log/lastlog: No such file or directory

Okay, it had more than that, but this is where the gap occurs.

Any ideas?