diff --git a/kallithea/lib/ssh.py b/kallithea/lib/ssh.py
--- a/kallithea/lib/ssh.py
+++ b/kallithea/lib/ssh.py
@@ -66,11 +66,8 @@ def parse_pub_key(ssh_key):
     >>> parse_pub_key(''' ssh-rsa  AAAAB3NzaC1yc2EAAAALVGhpcyBpcyBmYWtlIQ== and a comment
     ... ''')
     ('ssh-rsa', '\x00\x00\x00\x07ssh-rsa\x00\x00\x00\x0bThis is fake!', 'and a comment\n')
-    >>> # FIXME below test shows incorrect behavior -- to be fixed in a subsequent commit
     >>> parse_pub_key('''ssh-ed25519 AAAAC3NzaC1lZDI1NTE5AAAAIP1NA2kBQIKe74afUXmIWD9ByDYQJqUwW44Y4gJOBRuo''')
-    Traceback (most recent call last):
-    ...
-    SshKeyParseError: Incorrect SSH key - base64 part is not 'ssh-ed25519' as claimed but 'ssh-ed25519'
+    ('ssh-ed25519', '\x00\x00\x00\x0bssh-ed25519\x00\x00\x00 \xfdM\x03i\x01@\x82\x9e\xef\x86\x9fQy\x88X?A\xc86\x10&\xa50[\x8e\x18\xe2\x02N\x05\x1b\xa8', '')
     """
     if not ssh_key:
         raise SshKeyParseError(_("SSH key is missing"))
@@ -91,7 +88,7 @@ def parse_pub_key(ssh_key):
     except binascii.Error:
         raise SshKeyParseError(_("Incorrect SSH key - failed to decode base64 part %r") % keyvalue)
 
-    if not decoded.startswith('\x00\x00\x00\x07' + str(keytype) + '\x00'):
+    if not decoded.startswith('\x00\x00\x00' + chr(len(keytype)) + str(keytype) + '\x00'):
         raise SshKeyParseError(_("Incorrect SSH key - base64 part is not %r as claimed but %r") % (str(keytype), str(decoded[4:].split('\0', 1)[0])))
 
     return keytype, decoded, comment