At the end of the day, only you know how you are feeling. If you are not feeling secure about your standing in the company, it's for a reason. Starting your search now gives you the ability to negotiate from a position of power, as you can say no to an offer and wait for another better offer.

Now, WRT trusting your gut... You aren't in a position to know for sure how things will turn out with this company, and you won't know for sure until someone tells you ;) You deserve to be in a place where you feel secure.

If you feel insecure with hardly any reason, you’ll feel insecure anywhere so moving won’t help at all.

OP will probably feel a lot more insecure as the new person at a new company than they do at their existing company where they've already proven themselves and own multiple projects.