Your problem is most likely related to the underpowered or
over-provisioned HostGator shared servers. Since their purchase by EIG
last year, they've migrated customers to new hardware, and from my
experience (I host 40+ WP blogs with them) this new hardware or
provisioning rules has created poor performance for any site that relies on
MySQL such as WordPress.
Shared hosting is always a gamble as you rely on the hosting provider to
manage the number of accounts, and the performance as a whole. I've hosted
with HG for years and they've been great, but since late 2013 the
performance has been atrocious.
Caching is only a band-aid, as the core problem is MySQL performance and
the over-crowding of the server.
Find another (non EIG) shared web host, or upgrade to a VPS to give you
more control/protection from other customers.
Also, it's worth noting that Google XML Sitemaps plugin is a well known
resource hog, and is explicitly not allowed by high performance WP hosts
like WPEngine: http://wpengine.com/support/disallowed-plugins/