If you have the original ssh keys accessible somewhere, be sure they are loaded in your new machine’s ssh agent, then try again (windows notes, general notes).
If you no longer have the ssh keys, perhaps you granted access to other users/colleagues (i.e., added their public keys) and one of them could add your new public key to the server for you (e.g., add it to keys in this users list and reprovision).
Or, you could perhaps use your VPS provider’s web console to log in to the server and manually add your public key to /home/admin/.ssh/authorized_keys. For example, if your server is with Digital Ocean you could use the web interface and go to droplet > access > launch console then log in with the use user admin and the admin_user password from vault_users in your group_vars/staging/vault.yml file. If that isn’t working, you may have to go to droplet > access > reset root password – then it will email you a new password for root, like in the first half of steps outlined at Help with users on secured droplet