find leading zeros: performance
zeros or zeroes? Better make up your mind and stick with one.
str.join is good when you want to join an iterable. For two strings, just use +.
Instead of always reencoding and rehashing the input string, you can do it once and then copy the resulting hasher (state) for different extensions.
Instead of creating random bytes and then elaborately turning them into a string and back to bytes, just use the bytes. Since that's also just a single function call, you can ditch your gen_keys_06 and its overhead.
str.startswith is at least simpler, don't know about speed.
For measuring performance, create a benchmark that runs the function much more than just once, as a single time is rather random. Or change the function so it tries a fixed number of random extensions (let's say a million) instead of stopping at the first successful one.
You ask us &quot;On what should I work to make it faster?&quot;. That's a question to ask a profiler.
Producing random values takes time. Check the profiler's results (or leave out the randomness when doing the million-extensions thing) to see whether it's significant here. If it is, maybe try a different randomness source (I think I've seen someone say that os.urandom is slow on Linux). Or if you don't actually need randomness, try increasing bytes instead.
Do you really want zero-nibbles? Or would zero-bytes work as well, i.e., are you maybe really only interested in even numbers of zero-nibbles? Then you could use digest instead of hexdigest, which is probably faster because bytes are probably what the hasher actually works with and because it makes digests half as large and you'd check for fewer zeros.

A version incorporating some of those points:
def search_matching_random_str(input_str, zeros, _sha1=hashlib.sha1, _urandom=os.urandom):
    leading_zeros = &quot;0&quot; * zeros
    hasher_copy = _sha1(input_str.encode()).copy
    while True:
        my_random_bytes = _urandom(4)
        hasher = hasher_copy()
        hasher.update(my_random_bytes)
        hashval = hasher.hexdigest()
        if hashval.startswith(leading_zeros):
            return hashval, my_random_bytes