Why is it so slow?
Is it because my data is on HDD?
Or is it because the historical file database is placed on the HDD along with the files?
Or are these historical files not indexed at all?
This is a known problem (see https://github.com/syncthing/syncthing/issues/7393), however it should work relatively fine unless you’ve got thousands of files there, especially in a single folder that needs to be opened at once. If there are many files, but they are located in reasonable numbers inside subfolders, then the tree should still be usable.
When it comes to your questions, there is no database for the versioned files, so the GUI needs to check and index the folder each time you open the Restore Versions panel. The more files you’ve got there, the slower it will be, and especially on an HDD.