Cdtjkyj

I am unsure if I did the whole procedure right, so let's start with what I've done:

$ ssh-keygen -vvv -o -a 1000 -t ed25519 -f ~/.ssh/id_ed25519 -C "$(whoami)@$(hostname)--$(date -I)"

with some real strong password.

I successfully logged into my Debian machine using that key (-i /path/to/private/key).

I thought that's a success, so I've rebooted both machines and now my GNOME Keyring is empty on both Mint and Debian with me being unable to manually import the private key, I tried it:

I have found that Seahorse (GNOME Keyring) currently does not handle Ed25519 on ArchWiki:

The following citation was edited to be more up-to-date and to have various links to the Wikipedia and to be more readable.

As of January 2018, seahorse (GNOME Keyring) doesn't handle ECDSA {Bugzilla (RESOLVED FIXED), Wiki}, nor Ed25519 {Bugzilla (NEW), Wiki} keys. You can turn to other SSH agents if you need support for those.
(Source - look at the bottom).

Do I need to wait for a bug fix / enhancement, or is there an alternative approach for me not to have to enter the complex password or enter it maybe once upon login? I don't honestly know, what my choices are at the moment.

EDIT #1

I don't want to switch back to the ECDSA or RSA keys.

EDIT #2

I have installed Linux Mint 19.1 (clean install, no upgrade), which is based on Ubuntu 18.04, but the issue in the same manner persists.

The ed25519 does not show up in the Seahorse 3.20.0:

Listing keys:

for key in ~/.ssh/id_*; do ssh-keygen -l -f "${key}"; done | uniq

• 
  

  Server:

  
  
  

  256 SHA256:SMeBXPSluFwGBub/brKUy4/m8/DLim8Aw7zMmcdyEPs root@backup-server--2019-02-22 (ED25519)
  
  8192 SHA256:JKKvLs+LXOdgv5nr00YFGjywqGANEFwCjXnzcjJ87og root@backup-server (RSA)
  
  

  
  


• 
  

  Client:

  
  
  

  256 SHA256:WOj0Nl4svbiSxayTOCUC9LlI5nPQDyls9qV65u/0WwE vlastimil@dell-7577--2019-02-22 (ED25519)
  
  8192 SHA256:GWPe50O7U0xq3DsRaQewz4WhOLrZ64Vf4x5bKnelrX4 vlastimil@dell-7577 (RSA)
  
  

  
  

The fix for this issue is included in Gnome Keyring 3.28 and seems unlikely to be backported to earlier versions.

If you want to go ahead with Ed25519, then you will need to wait for a release of your favorite distribution that includes this version.

I see that the next release of Linux Mint, Tara, will be based on Ubuntu 18.04, which includes this version, so perhaps you will not have too long to wait.