What is the best way to store SSH fingerprints and public keys?
If I'm not mistaken, the fingerprint is a hexadecimal number.  That means you could store it as a binary number, since two hexadecimal characters can be represented by a single byte, making a 32-character hexadecimal string = 16 bytes.

Here's the documentation on binary and varbinary data types for MySQL 5.7 (I don't have a test environment handy).  

I do something similar for IP addresses based on this question and answer from StackExchange.  Store the data as binary, convert it back to text when it needs to be displayed or compared against another string.  Create a view that calls the functions as a part of it so you can easily get and store the full string when you want it.

Also, public keys are indeed public, and are often stored in searchable databases like this one.