I have a list of S3 keys for the same bucket my_s3_bucket.
What is the most efficient way to figure out which of those keys actually exist in aws S3. By efficient I mean with low latency and hopefully low network bandwidth usage.
Note: the keys don't share the same prefix so filtering by a single prefix is not effective
The two suboptimal approaches I can think of:

Check the existence of each key, one-by-one
List all keys in the bucket and check locally. This is not good if the total number of keys is large since listing the keys will still incur many network calls.

Is there any better alternative?
To answer your question: there is not alternative exposed by the S3 API.
Using multiple threads or asynchronous I/O are solid ways to reduce the real time required to make multiple requests, by doing them in parallel, as you mentioned.
A further enhancement that might be worth considering would be to wrap this logic up in an AWS Lambda function that you could invoke with a bucket name and a list of object keys as arguments.  Parallellize the bucket operations inside the Lambda function and return the results to the caller already parsed and interpeted, in one tidy response.  This would put most of the bandwidth usage between the function and S3 on the AWS network within the region, which should be the fastest possible place for it to happen.  Lambda functions are an excellent way to abstract away any AWS interaction that requires multiple API requests.  
This also allows your Lambda function to be written in a different language than the main project, if desired, because the language does not matter across that boundary -- it's just JSON crossing the border between the two.  Some AWS interactions are easier to do (or to execute in complex series/parallel fashion) in some languages than in others, in my opinion, so for example, your function could be written in Node.JS even though your project is written in python, and this would make no difference when it comes to invoking the funcrion and using the response it generates.
What is the most efficient way in python of checking the existence of multiple s3 keys in the same bucket?