The combination of SHA1 and package name is globally unique. So if you added your app to a previous Firebase project, you can't add the same app/signature to a new project. You mentioned that you can't find your old project. If you were the owner of the old project you can reach out to
Firebase Support who can help you find it. Or you can try to continue using Firebase without your SHA1 at all. Most features don't require it, it's mostly needed for Google Sign In and Dynamic Links. If you're just using Realtime Database and email/password sign in, for example, you don't need it.