PHP: Optimize Find-and-replace procedure of many strings in single string

I'm auto-linking profiles existing on my site in blogpost texts which contain the profile names. To do so I...

1) ...extract currently ~500 rows (only?) from 4 different MySQL tables - containing different types of profiles - in a single database using 4 individual queries.

2) ...str_replace() every profile name individually with a link in the blogpost text, if that profile name exists (tried putting them in search-replace arrays before and do a single str_replace() as well).

While it does what it is supposed to do, it slows down the Blogpost overview page significantly. Loading 10 Posts on the overview page, in which each content is checked against the occurence of profile names, takes 30+ seconds to load. Without this whole autolink procedure the Blogpost overview page loads quickly.

I believe the culprit is step 2). What can I do to speed up the process of finding and replacing a large number of strings (coming from a database) within a single text string?

Following @Devon's and @tadman's recommendations it's now the users obligation to take care of linking profiles. However I needed the option to link to profiles which do not exist at the time of post writing but which might be created later. Users now tag any existing or future profile when writing a post by including their name in curly braces. These are found by performing a preg_replace_callback and search the database for the profile name inside the braces.

private function link_profile($name) {
    // Put your database search(es) here
    // Create link to profile
    return $link_to_profile;
}

$text = preg_replace_callback("/\{(.*)\}/Usi", "link_profile", $text);

In my previous ressource-exhaustive ansatz there were up to 5N str_replace calls for N profiles in the database, since variations of the profile name where considered. Now there are between N and 4N database calls at most for N profiles marked in the post text, since 4 different profile types living in individual DB tables might need to be searched for. The new procedure decreases the Blog loading time to ~3s, marking an improvement by more than a factor of 10 compared to the former method.