Woocommerce (com muitos produtos) extremamente lento. O que fazer?

Olá, bom dia a todos! Antes de tudo, deixo claro que sou leigo e agradeço antecipadamente pela paciência, cordialidade e ajuda.

Tenho um site Wordpress com Woocommerce que possui somente 6000 visitas por mês e uma taxa baixíssima de conversão, em muito, por conta da grande lentidão do site.

A grande questão é que tenho neste woocommerce cerca de 40.000 produtos cadastrados para venda (e preciso que continue com essa quantidade). E é isso, isso é o site, basicamente. Nada demais.

O site está muito mal posicionado no Google.

O banco de dados MYSQL pesa cerca  de 600 mb.

O que fiz até aqui foi instalar o plugin de cache W3.

Comecei em uma hospedagem compartilhada. Não rolou pois parece que a alta quantidade de postagens(produtos) pesa.

Depois passei por duas VPNs, e não deu certo também. O site além de lento ficava totalmente instável e vivia saindo do ar. Tudo isso eu mesmo transferindo e levando na garra em hospedagens sem nenhuma adaptação específica para minha situação.

Por último, eu fui para uma Cloud Hosting da Locaweb com banco de dados dedicado na seguinte configuração:

4GB MEMÓRIA / 2vCPUs PROCESSAMENTO / Mysql Dedicado / 50GB espaço em disco  / Transferência ilimitada / Gerenciado por eles. (Pagando 329 reais por mês).

Foi a única que segurou o site, embora esteja ainda bastante lento para carregar.

A questão é que – na minha visão de leigo – intuo que dê pro site ficar mais rápido e até a hospedagem mais barata ou no mínimo – otimizada – pois o site nada mais é do que um wordpress morto com um woocommerce com 40.000 produtos cadastrados, sem grande complexidades (incialmente eu tinha cadastrado tags mas exclui todas elas pra diminuir o problema)

Os índices das minhas páginas no PageSpeed Insights do Google estão bem ruins, girando em torno de 30. Ao desativar os plugins e deixar só o essencial dá uma ligeira melhorada, mas penso que era pra essa hospedagem aguentar.

Simplesmente não sei o que fazer. Gostaria de uma luz, por favor.

Enfim, minha hospedagem não é otimizada para wordpress (não sei se isso faz diferença e quanto faz) , não estou usando nenhuma CDN (será que isso poderia fazer alguma diferença mesmo eu usando uma Cloud Hosting?) .

Não sei que tipo de serviço de otimização, ou hospedagem buscar, tendo em vista que sou leigo.

Em suma, gostaria de saber que dicas a galera poderia me dar, no que diz respeito à esta situação.

MUITO grato.