Should I just write it on a piece of paper? What do you guys use?
There is no safest wallet.Even the hardware wallet can be stolen and hacked due to human ignorance and the less secure wallet can be made secure by human intelligence.I would advice you to use cold storage if you want to hold large amount of bitcoin for long term and use hardware wallet if you want to do daily transactions.That should be sufficient and make sure the wallet you use for cold storage gives you access to your private keys.Paper wallet can be considered a safe cold storage option 