Yes, you should change your master password every few months. The answer to the rest of the problem is to use a password manager like LastPass or KePass. I use LastPass and it can generate passwords of just about any length and complexity and can log you in automatically if desired. Icon sits on the toolbar of your browser.
Here's a password I just generated:
![]()