Might be a harddrive problem. You said they replaced the MB, but problems there could have have affected subsystems. (like I said, tough to tell here) And HD problems will affect overall system speed. And I’m not talking about defrag issues. Defrag will help some, especially on an older system that’s seen lots of use, but for a relatively new system, and boot and basic system files, it should not be THAT BIG an issue. Now a CHKDSK on the other hand would not be out of line. Whatever you do, I’d back up the system. Full and complete. Also a separate back up of just data - C:\USERS\USER_ID, and where ever you store stuff, as an additional measure. Systems can be rebuilt, personal data can’t.
I bought an external harddrive that I backup once a week after the system crashed. They retrieved my data, but I learned a lesson.