About a third of my bookmarks changed to random sites I recently visited.

If you go to Manage Bookmarks library pane, does it show the links there correctly (and only wrong URLs are opened after clicking)? If you manually copy the misbehaving bookmark's URL from there, and paste it into a new tab/window, does it still end up opening the wrong site?

Restart into Troubleshoot Mode (via Help menu) to see how it behaves there.

If you go to More Troubleshooting Information page from Help menu look for "Places Database" and run "Verify Integrity" button.

They've changed in the Manage Bookmarks pane as well. The "name" column of the link is still correct, but all the URLs have changed. I also appears that it's continuing to happen because more bookmarks have changed since this post.

Normally I'd suspect malware but if you're saying it's sites from your own history that points to support.mozilla.org/questions/685303 — the places maintenance should however be able to spot any corruption.

There are bookmarks backups you can restore, however that usually means having to wipe history — see Can't add, change or save bookmarks - How to fix for some tips, and the sqlite rotation in the second half of that article.