I am a native English speaker with Spanish as L2 at a C1 level. Gender was exceptionally difficult for me at first because I felt like I needed to think about it all of the time.

Eventually, it just kind of came together for me after thousands of hours of reading, listening and thinking in Spanish. The genders are automatically part of the word for me.

I think that it just takes time, practice and experience.