Can you firstly check that you have the optimal caching settings: Never recompile (if you don't change stuff often and Recompile if modified if you do) / Cache - yes / File system / Clear cache when modified / CCC - all yes / Ciphering - PHP Enc / Server side cache - Yes (Redis or APC) / Full page - NO (it's broken)
Then if you can please share your server settings (memory limits, software versions, etc).
If everything here is OK we can then proceed with debuging by turning ON Profiling and Debuging and seeing what is showing there (but in offtime for your shop).
Also, I know that you recently migrated to this VPS but if it's on litespeed (I highly doubt) you can install a caching plugin that really speeds up the whole thing and it's free. If not on litespeed look around for such provider and when your current VPS expires better change to it.
Latest edge channel updates don't contain anything that can slow down our shops. datakick even introduces some minor speedups (that won't affect the shops with noticeable speed improvements too)