Suggestions for Magento hosting?

You should check out the Web Hosting Offers section of this forum, you will find good hosting providers there.

I would look into a managed VPS plan or at least a semi-dedicated plan to host your Magento site.

Hostgator is not where I would host a Magento site. You need good quality hosting. Start with Veerotech. They are active on here and offer above average customer service and quality hardware. Otherwise, look at something like liquidweb storm on demand. You never told us who it is hosted with right now...

For Magento Hosting I recommend Cloudways. You will get Varnish Supported Platform with best Cloud Hosting Service. Cloudways is an intuitive cloud hosting platform, that enables novices, bloggers, designers, developers and agencies to easily manage and deploy applications on DigitalOcean, Amazon EC2 servers and Google Compute Engine.

What Cloudways does is optimize and setup all the necessary software on the DigitalOcean, Google Compute Engine and Amazon EC2 servers. You don't have to worry about installing Linux, MySQL, PHP, Varnish, Memcache, Apache, Nginx and other scripts on the servers.

Prices start at $15/month.

Features of Cloudways Platform:

Installation
1- Selection from DigitalOcean (6 data centers) and Amazon EC2 servers (9 data centers) and Google Compute Engine (3 regions)
2- One Click Application Installs (WordPress, Magento, Drupal, Joomla, Prestashop, support for all php based applications)
3- Server scaling, based on bandwidth, hard disk space, processor and RAM.
4- Billing on hourly basis.
5- Free New Relic Addon
6- Rackspace Email Addon
7- Ability to change PHP Versions (5.4, 5.5, 5.6), install Redis, change MySQL versions to MariaDB.

Server Features
1- 15 real time monitoring features.
2- Vertical Server Scaling
3- Service Management (Nginx, Varnish, MySQL, Apache, Memcache...)
4- Advance Server settings (Upload size, execution limit, memory limit etc.)
5- SSL Certificate Configuration
6- Automatic Backups, with frequency as low as 1 per hour
7- Server Addons (Email settings)
8- Dedicated IP
9- Unlimited Domains
10- Unlimited Application Installations

Application Management
1- SFTP connection
2- Dedicated MySQL/MariaDB Database
3- Application Restore
4- Application and Server Cloning
5- Git Integration and Deployment Via Git
6- SSH Access

All servers are automatically updated and patched as soon as new updates are available. Also support team is available 24/7 to help and assist whenever needed.

Actually you need a new host that offers FREE migration service. OR look for a better host as already suggested here, then hire someone to do the migration for you.

I recommend Finestshops hosting for Magento , because i have been using Magento with them from three years and they offer best hosting plans at reasonable prices.