Наречие легитимно существует. Можно встретить такие обороты: легитимно избрать (избранный), легитимно бороться, легитимно действовать. Значение этого наречия соотносительно со значением прилагательного легитимный, от которого оно образовано: 'законно', 'соответственно закону'.

Прилагательные легальный и легитимный имеют разные значения. В данном случае - "полученный законным путем" и "признаваемый законом".

ЛЕГИТИМНЫЙ, -ая, -ое; -мен, -мна, -мно. [от лат. legitimus - законный, правомерный] Законный. Л-ая власть. 

ЛЕГАЛЬНЫЙ, -ая, -ое; -лен, -льна, -льно. [лат. legalis] Признанный, разрешаемый законом. Л-ая партия. Л-ая печать. Л-ое положение. // Использующий допускаемые законом возможности, основанный на использовании их. Л-ая форма борьбы. ◊ Легальный марксизм. Идейно-политическое течение (в последнее десятилетие 19 в.) части российской буржуазной интеллигенции, пытавшейся использовать для обоснования развития капитализма в России отдельные положения экономического учения К. Маркса. <Легально, нареч. Л. издавать газету. Легальность, -и; ж. Л. положения. 

Вы можете воспользоваться окошком "Искать на Грамоте".

Возможно, легитимный? Легитимный - находящийся в соответствии с действующим в государстве законом; законный.