I'd been considering something similar, never really made a PoC though.
How about this:
User provides their public key when they signup.
To authenticate, server produces a nonce and sends to the client, client signs the nonce with private key and sends the result, server verifies signature with public key.
Upon further consideration, this pretty much describes a an authentication method based on a client certificate. Unless i am missing something - i am not sure how to apply this to our problem space. We have traditional type of users who are used to username/password authentication. Solutions that we consider have to build on that as a fundamental model.
How about this: User provides their public key when they signup. To authenticate, server produces a nonce and sends to the client, client signs the nonce with private key and sends the result, server verifies signature with public key.