I currently wrote an API which uses HTTP Basic over TLS for authentication and I am quite happ y with it.
Now I bumped up the values for password encryption (like length, iterations, ...) to have a more realistic scenario. Unfortunately this made API access really slow as I have to rehash the HTTP Basic credentials over and over again.
What would the easiest approach be (beside of sessions of course) to overcome this problem?
pbkdf2 isn't meant to be called repeatedly, in fact, it's slow to prevent just that. This is generally combined with some session or token based authentication and SSL/TLS.
If your slowness is due to pbkdf2, and you don't want to do sessions or any similar token based authentication, then there's not much you can do here outside of abandoning or lowering the iterations for pbkdf2.
Though, you might consider abandoning HTTP Basic Auth, keep TLS though, and do your own authentication, then keep the connection open for additional requests. Of course, it's going to be up to the client to support this also.
Another solution would be to add more hardware to spread the load. Since the hashing is done on the web server and not the database server, you can add more web servers, web server CPUs, etc., and balance the load.