Contabo is quite known for overprovisioning. Not saying that is the issue, but always worth considering the hardware first. You don’t get what they promise, if more users use their service, you will end up having less resources available to you than you expect.
But since you also mention you tried locally too and have issues there too, i would suggest you run the following test:
Export the workflow that is causing issues, spin up a self hosted n8n instance in docker on your workstation which most likely is much more powerful than your vps.
Then import only that workflow to see how it performs. By the sound of it you have already tried this step.
The next logical step is to spin up a new docker with an older version of n8n, test the workflow again and see if its still slow.
That way you can find out if its, your hardware, the N8N version having a memory leak or poor performance, or if something in your workflow is misconfigured in some unlucky edgecase, that degrades performance significantly