Commands to install Apache, Mysql and PHP through ssh

Well when your profiling anything like this to find the bottleneck you need to rule things out one by one. You'll need a baseline to get comparisons against. If you have the "ab" tool installed (it comes with apache) you can use this.

To get your baseline I recommend getting the average of at least a couple of hundred requests. Here's an example:

$ ab -n 400 http://yousite/

Look through the results for the line of "Time per request", it'll look something like:

Time per request:       96.031 [ms] (mean)

Make note of that time as this is the baseline.

To rule out apache as the culprit make a static page on your server (just save the html of a page that you consider slow/sluggish) and run ab against it again.

Throw some PHP into the static page. It doesn't have to be a large amount of it but it should be actually doing some work. MediaWiki is pretty good code so if there is a PHP bottleneck on your system my money would be on the actual loading of the PHP stack into memory and perform the test again.

Look at the three numbers and see where the biggest jump is between the next step up. My bet would be on MySQL being the slowest of the three but it could very well be that you are loading up a lot of images on a page that is slowing down the total request time in which case you might want to rethink the design of the page.

All of that would run just fine, except for MySQL.
I recommend you get another MySQL host, as MySQL takes up to 220MB of RAM om my VPS while idle, that's why I switched to SQLite.