There are several ways to do this, depending upon how complex you want to get. For example, you could go all the way of implementing an OAuth2 service and having your servers authenticate with each other, but that would probably be overkill. Given the description you gave of your situation, something simple would probably work well, in my opinion.
Essentially, what you need is a way of modifying the request, so that each server can be reasonably certain that the connection coming in is from a trusted/authorized source: your other server(s). There are many ways to do this. One straight forward way would be to simply inspect all connections and only accept connections from a given list of IP addresses, but this doesn't provide any authentication guarantee (anyone on that IP is given access), and is also vulnerable to IP Spoofing, but depending upon how much you care about things like that, that might be enough for you.
One way of doing the shared key thing you asked about is just to have a big random string/number (essentially acts as a token/API Key), and add it to all requests as a header (or URL parameter), and the receiving server can just extract the header and do a basic check on the string to see if the string is an exact match. If the "password" header is exactly the same as the password on the receiving server, it assumes that the request is valid, and processes the request. If not, it simply aborts and drops the request. However, if someone intercepts the request and manages to find your password, they can submit their own requests by simply passing the same password. I don't think you mentioned what language/frameworks you are using, but if you're using Java & the Spring framework, you can create Interceptors & Security Filters which automatically catch all requests as they come into the server before they're processed, which allows you to handle things like this, so you don't have to do it over and over again in every controller mapping. Other frameworks have similar features, but I have most experience with Spring.
If you wanted to get a little more fancy, you could go with a JSON Web Token (JWT) using a shared key, and append it to each request in the header. Then, just like before, you can inspect the request headers to extract the Token, validate it, and then process the request. JWT's have the added benefit of built-in validation & tamper protection, as well as allowing custom data fields to the token, so you could start to add more information to the token, like timestamps, types of requests, levels of clearance, user ids, etc. and they would all be encapsulated in the token, and protected by it's validation & tamper protection. If you're using Java, there is a pre-built, very easy to use JWT library called JJWT (i.e. Java JWT). Here is a video on it:
Starts @31:36
https://www.youtube.com/watch?v=sv0TUiYVimw
Here's the maven Dependency:
<dependency>
<groupId>io.jsonwebtoken</groupId>
<artifactId>jjwt</artifactId>
<version>0.7.0</version>
</dependency>
As for the rolling (i.e. constantly variable) password, you could do that pretty easily. Something as simple as Encrypting a timestamp with a shared key, and sending it in a header on the request (or adding it to the JWT). Then the receiving server would just decrypt the header and check the timestamp. If the timestamp is older than 1-5 seconds (depending upon the latency between the servers and variance in clock times) the receiving server just aborts & drops the request; you could respond with an HTTP status code of "Unauthorized". If the server tries to decrypt the timestamp but fails due to corrupt data (or someone trying to spoof the header) or if the header is empty, the server should also abort, and drop the request.
Not to sound like a broken record, but if you're looking for a simple encryption API, Spring also has an easy one in their Crypto package, but it defaults to AES-256, which requires the unlimited strength encryption Policy files installed on your JRE. They're free & easy to install (just download from oracle, and paste them into the right directory), but it's something to be aware of. Without the policy files, it will throw an error: "Invalid key length" or something like that. It just means that it's trying to use encryption that's too strong for what the JRE allows; it has to do with US export control laws. But the short of it is that any American Citizen can download them for free.
What you're trying to do basically sounds like a small scale micro-service. You might be interested in these talks:
https://www.youtube.com/watch?v=ZyK5QrKCbwM
https://www.youtube.com/watch?v=rqQOSG0DWPY
https://www.youtube.com/watch?v=sbPSjI4tt10
https://www.youtube.com/watch?v=saiwZzE5IYg
Hope this helps.
-Yurelle
Edit: Also, you mentioned that one of your main concerns was the performance issues with people spamming your API. You're essentially referring to a small-scale Denial of Service attack. From your minimal concern with security, I get the impression that the project you're working on is somewhat small scale and you're not expecting to be the target of any serious attacks; and that it's more of a Better-Safe-Than-Sorry precaution, which is always good, I'm certainly not faulting you. However, if you ever do expand into the territory of being in serious danger of such attacks, there is one type of attack that many people often forget about; It's called a "Slow Loris Attack". It's very simple to pull off, and it's extremely effective given the resources necessary to run such an attack, and, to my knowledge, the only reliable defense is a non-blocking web server framework (often called "reactive" or "event-based"/"event-driven" frameworks). Again, probably not something you need to worry about, but since you brought it up, I thought I'd mention it.
Here's a video on it, if you're interested:
https://www.youtube.com/watch?v=XiFkyR35v2Y
