[wickedshimmy]

This is a very good point, and is the sort of situation where API tokens can come into play and be useful. A client can make a single request to "open a session" and receive a short-lived key that is used as the password credentials for subsequent requests. Store active keys - since they are short-lived, offline attacks are less of a concern and you can probably choose to not slow-hash them. When the token expires and a request fails authentication, the client simply requests a new one and retries. The token lifetime is a much easier adjustment for which to weigh security versus performance/load considerations, compared to against broader password storage security.

[poutine]

You've described OAuth in part with its refresh and access tokens.