This is actually not a problem as such: since you deleted your
known_hosts file, SSH client's memory of previous connections to Github is gone, and now it behaves as if you're connecting to Github for the first time. So it cannot automatically use Github's host key saved in
known_hosts to verify the supposed "Github" is the same server as before, and not an imposter. This fingerprint is of the remote host's SSH host key which is not affected by anything you did locally.
Now, to verify that you are connecting to a real Github and not to a fake one, you would have to verify the fingerprint yourself and answer
yes to the question, or just copy&paste the fingerprint you got from another source (like this webpage of GitHub.com).
After the fingerprint is successfully verified (or you just answer
yes to choose to trust it), the actual remote host's public key will be saved to your
known_hosts file, and on next connections the verification will happen automatically again.
However, I note that the fingerprint you are seeing does not actually match GitHub.com's SSH public host key fingerprints. Either you are connecting to your own private GitHub instance, or there is a man-in-the-middle between you and the real GitHub.com.
The authentication with your ed25519 key pair has not even started yet: first the remote host key is checked to see if the remote host is already known (and if so, it's used to verify the remote host's identity) and only after that is successfully done (or the user has explicitly chosen to trust the remote host), SSH will start the process of authenticating you to the remote host.