A VPN is not likely to make anything go faster unless it’s redirecting you to a different, equivalent target server and the problem was at the original target server, but the problem could be one of bad routing between the ISP’s core routers and that server. Anyway, this is not a reason to switch ISPs randomly, when the problem hasn’t even been diagnosed yet, and in any case a choice of another cheap ISP is likely to be poor (slow), that’s why they’re cheap. I’m afraid that to a certain extent you get what you pay for, although there are most certainly other factors in the costs of running ISPs. And a new cheap ISP may be just the same as the last one if you are really unlucky.
The first thing to do is to traceroute over a representative path and show us the results. You should also have a good moan at your current ISP and ask them why they are slow. A routing problem is their fault, or further upstream, but anyway it’s up to them to either fix it or liaise.
You talked about Zen. Zen is a perfect example of a quality ISP that runs a high speed network because they have invested in their systems and who don’t just think in terms of race-to-the-bottom cost undercutting. They would be a good choice.