Hi everyone. I'm a new vegan. I'd like to be healthier and get into shape, and I figured this was the place to start

I'm not new to veganism, my girlfriend has been vegan since we've been together, about 3 years now..and I do a lot of the cooking (separate meals! that's romantic), and I'm not new to fitness..I've been a gym goer for years now, and I had a stint in the military - but I am new to vegan fitness.
I'm not fat, I'm not skinny.. I've lost a lot of muscle mass that I had before, and I'm out of shape. It really sucks and feels horrible. I still exercise but I don't see results anymore. I'm 26 and I'm too young to have old-man-itis! I want to see results and to feel better. I think this is a step in the right direction.