[mrb]

Use ECC keys or DSA+Elgamal keys. They are 100-150 bytes. That's just 5 lines of text when printed by paperkey. Much smaller than two full A4 pages!