Store suddenly SLOW to load and navigate

Cannot figure out why my Zen cart is suddenly painfully slow to load and navigate (more often than not). Is it most likely to be on the server side? My host did recently upgrade their servers and since that time, after reconfiguring my files, it seems to be this slow.
https://www.thedealsdiscount.com.
It used to jump quickly to an item when clicked. Now it is very sluggish. Any suggestions would be greatly appreciated.
Thanks!

Probably the server. Might specifically be the database, but without knowing the breakdown it's hard to tell.

So, first turn on Page Parse Time display, so you can see the whole-page-time and query-specific portion of that time, in the footer of each page:
admin > config > logging > Display The Page Parse Time > set to true
Explained more here: http://www.zen-cart.com/content.php?145
Post back with the numbers you get on various pages, like home page, product-listing/category page, product page, privacy page. The differences between those kinds of pages can be revealing.

Then you could work through this checklist: http://www.zen-cart.com/content.php?63-how-do-i-speed-up-my-site