I suppose keeping both paper and digital copies of your keys would provide the most security, but, it is a valid point that the more places you have your passwords, the higher the odds are that you could have them stolen.
I think caution and being conscience of your actions is the best guard against scammers and thieves.
If a business did pop up that specialized in keeping of personal keys and passwords, I would not envy them. They would immediately have a target on their back.
You could print them and store them in a sealed envelope. What I have done is to encrypt the keys before printing it, but giving my inheritors the instructions on how to decrypt it. A person with some encryption skills would probably be able to crack it, but of course there will be no way to know that these are actually passwords/keys and not just some random stuff. It's note like I have written "STEEMIT PASSWORD" on the envelope :P