We sent them over 200 pages of communication like chats and call histories last month. Now they are asking for travel history after marriage but we couldn't due to Covid restrictions. Not sure what to do now.
You neglected to mention this submission of communications - was there a previous additional document request? Was this submission responding to that request?
You may wish to put more of the meat of the text of the PFL (procedural fairness letter) here - just remove identifying information.
As for travel history, you will of course make the case that covid has prevented you from additional travel to see each other. But that's going to be looked at in the context of your full relationship (travel and living together before and after marriage); you had nine months of pre-covid period after your filing and you do not mention when you were married or other information, so hard for anyone to comment more.
The procedural fairness letter (PFL) is quite serious and is often (usually?) sent prior to a refusal, which you can appeal. But in preparation, you may wish to speak to a lawyer - appeal is a long and difficult procedure and it may be preferable to not appeal but to 'correct' the parts of your relationship proof that you can and file anew. (I do not know the appeal procedure well)
You can respond to the PFL yourself without having a lawyer do it but there are cases where it may make sense to have assistance of a lawyer, or consult with a lawyer before you respond to help identify what you need to focus on.