SSH failing to connect, No supported key exchange algorithms

Question

There are numerous questions with the same title however none of the solutions apply to my issue. I get the following lines of error in my sshd log:

Jan  6 21:57:55 <computer name> sshd[30103]: Received signal 15; terminating.
Jan  6 21:57:55 <computer name> sshd[30175]: Server listening on 127.0.0.1 port 22.
Jan  6 21:58:00 <computer name> sshd[30184]: error: Could not load host key: /etc/ssh/ssh_host_ed25519_key
Jan  6 21:58:00 <computer name> sshd[30184]: error: Could not load host key: /etc/ssh/ssh_host_rsa_key
Jan  6 21:58:00 <computer name> sshd[30184]: Disabling protocol version 1. Could not load host key
Jan  6 21:58:00 <computer name> sshd[30184]: fatal: No supported key exchange algorithms [preauth]

But the key files /etc/ssh/... exist and have the right permission: running la /etc/ssh/

total 276K
-rw-r--r-- 1 root root 222K Jan  6 22:01 moduli
-rw-r--r-- 1 root root 2.2K Jan  6 20:45 ssh_config
-rw-r--r-- 1 root root 2.8K Jan  6 21:57 sshd_config
-rw------- 1 root root  464 Jan  6 21:23 ssh_host_ed25519_key
-rw-r--r-- 1 root root  109 Jan  6 21:23 ssh_host_ed25519_key.pub
-rw------- 1 root root 3.3K Jan  6 21:24 ssh_host_rsa_key
-rw-r--r-- 1 root root  753 Jan  6 21:24 ssh_host_rsa_key.pub
-rw-r--r-- 1 root root  338 Jan  6 17:44 ssh_import_id

I've recently change my configurations to make it more secure. I've tried regenerating all key files but no luck. The client is the same machine (Trying to connect to ssh localhost) but no luck.

Solution

Ok I think I found the issue. I removed the server and re-installed it. If I let the generted key files rsa and ed25519 stay it works. If I remove and regenerate them with the following command it BREAKS

ssh-keygen -t ed25519 -f ssh_host_ed25519_key < /dev/null
ssh-keygen -t rsa -b 4096 -f ssh_host_rsa_key < /dev/null

EDIT Finally found the real issue. If I put passphrase on my keyfiles then it won't work and I'll get the error that connection is closed.

Comments

[Michael Hampton]

And what changes did you make?

[fukawi2]

Whatever changes you made, undo them and redo them one at a time until you find the specific change that breaks your connections. Then ask a specific question with details of the change.

[Arijoon]

I just restricted the algorithms and keys formats used. Host and client (which are the same machine) share a similar config file therefore they must be compatible

[Arijoon]

What's the reason for downvote? That's why nobody posts new questions that often anymore!

[EEAA]

Lemme guess - you followed the instructions in this article without understanding what they actually do...

[Arijoon]

I understand the client related part but not the server side!

[Arijoon]

Aside from guessing do you know how to fix this issue and use HostKeys with passphrase?