Again, while DNS failover is the simplest approach, you cannot overcome caching issues.
You can set the TTL time for your records to a much lower amount. 300 or 500 seconds. If 5-8 minutes is to big of a window to be down, then your only option is to see if you can find a provider that is present in multiple different locations and that will assign anycast IP's to those VPS'.
Even that has the potential to have some down-time though (Ex: If the provider continues to advertise the prefix at that location because just your VPS out of many sharing that same network segment is down).
The only way to be absolutely 100% certain of no downtime is to advertise your own prefix via BGP from the VPS itself. That way if it goes down, it will automatically withdraw the route. That's the only way you can take DNS caching out of the equation.
You could use a load balancer, but that brings in another single point of failure which defeats the purpose...