DB Maintenance at Logon taking too long

[PakRicard]

Hi all:

We are facing a increase of time needed to perform the DB maintenance at logon and it is becoming annoying as (as example) today it took 18 minutes to finish when used to be 2-5 minutes some weeks ago.

DB is hosted in a shared server at Hostgator. All other DB are working fine, time is OK, checked with Hostgator and seems like server side is 100% ok.
DB size (when backing up) is around 675 Mb.
DB Maintenance set to weekly.
webERP version running 4.09.1.
Via PhpMyAdmin it takes only 4,5 minutes to copy the whole DB into a new one.

Some questions:
1) The DB maintenance routine, has it been changed, improved, modified lately (last few months)?
2) Is there any trick to make it faster?
3) Is it a "must do" maintenance? Does it really improve efficiency of the database?