.htaccess url parameter rewrite for specific page

I have been battling for hours now and searched Google and StackOverflow, without a solution to my problem, hope you guys can help! :-)

I have a page with parameters as follows: profile?userid=123456789. I want it to rewrite to profile/123456789. This I have, but now everywhere on this page all links gets /profile/link. Is there any fixes to this? Thanks in advance, here comes my .htaccess code.

RewriteEngine on RewriteCond %{REQUEST_URI} !/profile.php

RewriteRule ^profile/([^/]*)$ /profile?userid=$1 [L,QSA]