Johnny Cloud gets a romantic interest in his second book length story, in All American Men of War 107 (Jan/Feb 1965), by Kanigher and Novick.
Because his story has the room to do so, we get a long flashback montage of Johnny Cloud and Running Deer, growing up together on the reservation and falling in love. He left to join the army, but she has as well.
For her troubles, she has been kidnapped by the Nazis. There is a special Nazi “magnet plane” in this story, which guides the pilots to their targets. Johnny’s target, on the other hand, is a Nazi rocket base. The Happy Braves believe they have destroyed it, but in fact the one they bombed was a fake.
Johnny rescues Running Deer and steals a magnet plane. Using the magnet plane to direct the other German flyers, he manages to get the Nazi pilots to bomb their own rocket base.
Running Deer sticks around, be coming a regular supporting cast member.