Have you been using VPS before you changed hosting company? They should tell you the source machine behind VPS. VPS is controled by one physical server hosting multiple virtual servers. To sum it up, you probably get 20% or less of dedicated power. Single core 4gb ram dedicated would perform a lot better than a VPS you are using.
Now the main question is, what those users do on your board, what kind of traffic they generate, what is mysql usage? Not all extensions are resource friendly given that they are still in development or have no indexing for some parts. Try disabling one by one extension to find possible culprit.
Board with 500+users active at the same time won't work with a VPS. You would need a low to mid end dedicated server with SSD.
You can also play with SQL logs, especially slow.log to see which queries are taking more to execute and therefore eating more power.
That being said, not every hosting company has same VPS plans and performance they claim to have.
"What would happen if the autism gene was eliminated from the genetic pool?
You would have a bunch of people standing around in a cave, chatting and socializing and not getting anything done."
- Dr. Temple Grandin, A Personal Look at Autism and Asperger's Syndrome.