Cannot connect using new SSH key (rsa 4096)

For an unknow reason, my work insist on using RSA 4096 ssh keys (even if they don't have passphrases) and therefore wants me to create a new pair (old current one is 'only' RSA 2048 with strong passphrase)

So I've moved my old pair to .ssh/id_rsa_legacy and .ssh/id_rsa_legacy.pub, then I created a new one with

ssh_keygen -t rsa -b 4096 -o -a 100

Sounds good so far, but wait !!!

If I do

cp ~/.ssh/id_rsa_legacy.pub ~/.ssh/authorized_keys && ssh localhost

I can connect, but if I do

cp ~/.ssh/id_rsa.pub ~/.ssh/authorized_keys && ssh localhost

I get an error

sign_and_send_pubkey: signing failed: agent refused operation

Also, ssh-add -l shows both keys (old one first, then new one)

I've looked on stackoverflow & duckduckgo but all answers discussed adding the new key to using ssh-add which doesn't solves my case.

Know someone who can answer? Share a link to this question via email, Twitter, or Facebook.