Extremely slow loading

Howdy!
I could really need some help.
Our site dolcevita.no loads extremely slowly (10-15″), espescially the admin part (20-60″ – sometimes timeout), but also opening pages in a web browser.
I see there are several people asking about this, but hardly any answers, and all questions are old – so I wonder:

• Is this a WP 2.5 issue? (sorry, need to find a plugin replacement)
• Is this likely to be a host problem? (it started after some server problems)
• Could it be a MySQL problem? (they’re still on version 4(?))
• Any cache plugin recommended? (WP super cache broke my site once, so – any other?)
• Any experiences with slow loading of admin pages on Macs? (It seems to quicker on Windows)

Dolcevita.no is a quite big site with light images but quite many plugins (30+) and also many widgets (50+)
Any help is really apreciated!
Kjetil