Since other posters already suggested good ideas, I'd like to share one sort of "unorthodox" way of storing your mnemonic phrases.

Memorize it. Yes, you heard that right. A 12-word recovery seed is a lot easier to memorize that most people thought(though memorizing 24-word seed is still possible, just significantly harder). But I understand that this is definitely not for anyone.