While both valid and legitimate can be used in this context, the problem with them is that, in the present-day usage, they involve a certain amount of ambiguity. Sometimes, one may say that a concern is valid or legitimate when one in fact shares it, and thinks that everybody should. Sometimes, however, saying that a concern is valid or legitimate, if its meaning were fully explicated, would amount to something like this:
It is perfectly understandable that you have this concern. You should
not feel that is silly or crazy to have this concern. You have every
right to express this concern and to have other people
listen attentively to what you have to say about the matter. I am, however, not
saying anything at the moment as to whether everybody ought to have
that same concern, or whether I, in particular, have it.
If one wants to convey the idea that there is something rationally compelling about the concern, and that everybody ought to share it, then well-justified concern is more likely to accomplish the purpose unambiguously. What would probably be even better is to not insist on an adjective, but instead say something like 'a concern for which there are good reasons'.