I had the same on SuSE after an upgrade.
What could be the problem is ksycoca who's rebuilding it's database, everytime kde starts.
You can try to remove the file ksycoca from either ~/.kde/.. or ~/tmp/.. (depends on where your version of kde puts it) and start kde again.
The first time kde will still start slow, but afterwards things should be back to normal.
If this doesn't work, it's possible that some other configuration files of KDE are corrupted. Either rename ~/.kde or use a test user to see if KDE starts quicker without your current configuration files.
Rinse[/code]