This is one of the exact reasons I created WSUS Automated Maintenance.
There is much to do - it's not just as simple as running the re-indexing script (although it does help).
Are you performing the proper WSUS maintenance including but not limited to declining superseded updates, running the Server Cleanup Wizard (SCW) (which you mention isn't working), running the SQL Indexing script, etc.? Did you optimize WSUS with Indexes, adjust IIS options? Have you done all of the maintenance documented by Microsoft?
https://www.ajtek.ca/wsus/how-to-setup-manage-and-maintain-wsus-part-8-wsus-server-maintenance/