Чем больше база даных, тем дольше грузиться страница.
 

Из-за чего может быть проблема?

база даны
тем дольше грузиться страница.

Медленный инет + не компактный скрипт имхо

Скорее всего запросы к БД не оптимизированны, да и вычисление внутри запросов идет. Плюс не сделанно кеширование данных.

1) Не оптимизированы запросы
2) Не рациональная структура базы

Посмотри планы выполнения запросов и выбери наиболее подходящий + сделай индексацию по тем полям, по которым наиболее часто идет поиск и тп (если у тебя преобладает выборка).

1)Индексы попробывать раставить в таблицах, если база поддерживает индекс. (Если честно, мне ещё не встречались таки сервер база данных, которые это не поддерживали, да и не интересовался этим особо)
2)Сделать более сткруктурированную базу/таблицы.
3)Покавырять запросы ...
4)... Сами скрипты или сервер базы данных, если на это права есть :)
5)Делать кеширование запросов/результатов или даже страниц