I can’t help with the switch wiring, but I can help with the wiring configuration. Because you only have one three-wire in each switch box, that suggests that you have power to the light with the light in between the two switches. Normally, one box would have a constant black hot (which would be the “Line”) but in your case it seems to be the red instead.
I would pull the light and look at the wiring there. You should find a two-wire where the black is always hot, and two three-wires going to the lights if I’m correct.
The reason you think that what you think is your “Line” not hot all the time is because that’s not the “Line”. It’s one of the travelers being energized only when the other switch is in one position only. More than likely, the “Line” is the constantly hot red in Box B.
