For troubleshooting you can ssh in verbose mode. (ssh -v -i /path/keyfile user@host). In the output, check which key is getting used to connect.

Comment out entries of the host, if existing in ~/.ssh/config

Move the old private key in your system to another directory and check if you can still login with old ssh key.