I updated my private key and added the public key to the authorized_keys on my target hosts and it didn't work. I ran a few verbose connections to see that the key was being sent, but not accepted.
Turns out the old version of ssh on this server doesn't generate the public key from the private key, it reads the id_rsa.pub file to send the public key. Since this public key doesn't match what's in authorized_keys, I was denied.
The solution was to delete the public key. Alternatively, you can generate the public key with ssh-keygen.