Extremely slow WordPress website with 6000 posts

I have a website with 6000 posts and it is extremely slow.

Sometimes I get this error in my browser:

Service Temporarily Unavailable

The server is temporarily unable to service your request due to maintenance downtime or capacity problems. Please try again later.

Error: 503 Service Temporarily Unavailable

I have turned almost all plugins off and it is slow in frontend and in backend too, so I guess it is not because of the template.

Could it be because of WP_navigation plugin?

I have est. 600 pages with ten posts or WP navigation plugin, could this be the problem?

WordPress can be a resource hog if you don’t use caching. W3 Total Cache could help you a lot with MySQL, Object and Page Caching. You should also install PHP-APC and use it with the plugin. It can do wonders.