Probably converting to Base36 and using the NATO phonetic alphabet would be better (alpha, bravo, charlie... one... zero). It's 5.16 bits/symbol, so only 0.7 bits/symbol less than Base58. Mmmmh secp256k1 is 279 + 65 bits. Base58 adds 32 bits for the crc (technically a truncated sha256) and I think 32 bits is the minimum we should add (but someone has noticed that sometimes you can change a single symbol and still the crc won't change, but if you save both private and public key this shouldn't be a problem... I think you can check if they are "connected" one to another so you could ignore the crc.), so it's 376 bits = 73 NATO "words" to save both public and private key together OR 352 = 69 NATO "words" without the "CRC". Made a test... Writing 4 "words" per row, 2 columns, on a Letter sheet with 0.5 inches of margin you can put 4 public/private "couples" at Arial 12 without any problem.