If the service access performs many requests, and each request has to be authenticated, this would be the expected behavior if an authentication cookie is not set. If every request has to perform a full authentication, performance will be noticeably degraded.
If you are unable to set an auth cookie, and you can use Windows authentication, IIS has a setting to only authenticate the first request.
You may experience slow performance when you use Integrated Windows authentication together with the Kerberos authentication protocol in IIS 7.0
http://support.microsoft.com/kb/954873
http://stackoverflow.com/questions/10783440/slow-performance-when-accessing-msmdpump-dll-with-basic-authentication-repeatedhttps://stackoverflow.com/questions/10783440/slow-performance-when-accessing-msmdpump-dll-with-basic-authentication-repeated