Paul

I use lastpass (it just makes things easier).

Dont get paranoid about it because of the doom merchants.
You may as well stop using the internet if you worry so much.
Just make sure you have a very strong password on your lastpass account.

I used to store them in a password protected excel spreadsheet, and still keep that up to date as a backup.