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.
$ ssh-keygen -y -f ~/.ssh/id_rsa > ~/.ssh/id_rsa.pub
I noticed that the ssh on my workstation doesn't read the id_rsa.pub file, so it must be an issue with the older ssh on the server (hosted server, I can't update it)