Faits: A. A.a. Par contrat d'affrètement du 3 septembre 2010, B._ SA, sise à Y._ (France), en qualité d'affréteur, a chargé A._ Ltd, sise à Z._ (Bahamas), en qualité de fréteur, de transporter une cargaison de blé. Suite à un retard dans le déchargement de la cargaison, A._ Ltd a adressé à B._ SA le 23 mars 2011 un décompte final avec un solde en sa faveur de 2'356'115,36 USD, représentant, selon elle, les frais de fret, ainsi que, à titre de dommage supplémentaire, l'indemnité de détention et les surestaries. B._ SA a refusé de payer le montant réclamé. A.b. Le 29 août 2011, A._ Ltd a requis un premier séquestre des biens de B._ SA, faisant valoir une créance de 2'356'115,36 USD avec intérêts à 3,25% dès le 23 mars 2011, à laquelle elle a ajouté des montants de 15'190,21 USD, à titre d'intérêts courus sur les indemnités de retard jusqu'au 23 mars 2011, et de 8'000 euros, à titre de frais liés à la procédure arbitrale. Le 30 août 2011, le Tribunal de première instance de Genève a ordonné, sur la base de l'art. 271 al. 1 ch. 4 LP (lien suffisant avec la Suisse), le séquestre n° 1 en mains de X._ SA, à Genève, de tous avoirs et biens, propriété de B._ SA, en garantie de créances de 1'908'453 fr. 44 (contrevaleur de 2'356'115,36 USD) plus intérêts à 3,25% l'an depuis le 23 mars 2011 avec capitalisation trimestrielle, 12'304 fr. 07 (contrevaleur de 15'190, 21 USD) et 9'440 fr. (contrevaleur de 8'000 euros), les titres invoqués comme fondement des créances étant le contrat d'affrètement du 3 septembre 2010 et le décompte final/facture adressé (e) à B._ SA le 23 mars 2011. Statuant sur l'opposition formée par B._ SA, le tribunal a annulé cette ordonnance par jugement du 15 novembre 2011. La Cour de justice du canton de Genève, en date du 10 février 2012, puis le Tribunal fédéral, en date du 2 novembre 2012 (arrêt 5A_222/2012), ont successivement rejeté le recours interjeté par A._ Ltd. A.c. Le 29 juin 2012, A._ Ltd a adressé à l'office des poursuites une réquisition de poursuite n° 1 en validation du séquestre n° 1, en indiquant comme titre de la créance le contrat d'affrètement du 3 septembre 2010 ainsi que le décompte final/facture adressée à B._ SA le 23 mars 2011, les intérêts courus sur les indemnités de retard jusqu'au 23 mars 2011, et les frais déjà établis dans la procédure arbitrale. B. B.a. Parallèlement à la procédure de séquestre précitée, A._ Ltd a ouvert action en paiement des créances fondées sur le contrat d'affrètement. La Chambre arbitrale maritime de Paris a rendu, le 26 juin 2012, une sentence par laquelle elle a condamné B._ SA à payer à A._ Ltd la somme de 2'047'235,36 USD - le décompte global de fret de 2'356'115,36 USD présenté par A._ Ltd a été réduit d'un montant de 308'880 USD car le tribunal a estimé que la durée des surestaries devait être réduite de 19 jours 19 heures et une minute -, avec intérêts à 3,25% l'an dès le 14 avril 2011 avec capitalisation trimestrielle, ainsi que 8'000 euros à titre de frais. B.b. Le 31 juillet 2012, A._ Ltd a requis un second séquestre des biens de B._ SA. Le même jour, le Tribunal de première instance de Genève a ordonné, sur la base de l'art. 271 al. 1 ch. 6 LP (titre de mainlevée définitive), le séquestre n° 2 en mains de X._ SA de tous avoirs et biens, propriété de B._ SA en garantie des créances de 2'004'897 fr. 50 (contrevaleur de 2'047'235,36 USD) avec intérêts à 3,25% l'an depuis le 14 avril 2011 avec capitalisation trimestrielle et 9'610 fr. 40 (contrevaleur de 8'000 euros) avec intérêts à 5% l'an depuis le 27 juillet 2012, le titre invoqué étant la sentence arbitrale étrangère précitée du 26 juin 2012. L'office des poursuites a notifié le procès-verbal de ce séquestre à A._ Ltd le 16 août 2012. C. C.a. Par courrier du 17 septembre 2012, l'office a informé A._ Ltd que, dans la procédure de séquestre n° 2, il n'avait pas connaissance de la validation du séquestre par une poursuite ou une action au fond. Il l'invitait dès lors à se déterminer à ce sujet, faute de quoi le séquestre serait levé le vendredi 28 septembre 2012 à 9 heures. Par courrier adressé à l'office le 21 septembre 2012, A._ Ltd a répondu que ce séquestre avait été validé par anticipation par la réquisition de poursuite n° 1 du 29 juin 2012. C.b. Par décision du 28 novembre 2012, l'office a constaté que le séquestre n° 1 ( recte : 2) était caduc, au sens de l'art. 280 ch. 1 LP, faute d'avoir été validé dans les délais légaux. Il a motivé sa décision en retenant, premièrement, qu'une poursuite antérieure ne peut valider un séquestre qu'au for ordinaire et, secondement, que, le séquestre n° 1 ayant été annulé, la poursuite n° 1 était nulle et ne pouvait donc pas être utilisée pour valider le séquestre n° 2. C.c. Par arrêt du 14 mars 2013, la Chambre de surveillance a rejeté la plainte déposée par A._ Ltd contre cette décision. D. Par acte du 25 mars 2013, A._ Ltd exerce un recours en matière civile contre cet arrêt. Elle conclut principalement à sa réforme, en ce sens qu'il est constaté que la poursuite n° 1 requise le 29 juin 2012 et le second séquestre n° 2 prononcé le 31 juillet 2012 sont valables et que l'office des poursuites de Genève est invité à l'informer des suites qu'il a données à la poursuite n° 1, et subsidiairement au renvoi de la cause à l'autorité cantonale en l'invitant à compléter l'état de fait et à rendre une nouvelle décision. En substance, elle se plaint de la violation de l'art. 279 al. 1 LP, voire de l'application arbitraire de cette norme, ainsi que d'arbitraire (art. 9 Cst.) dans l'établissement des faits. Invités à déposer leurs observations, l'intimée a conclu au rejet du recours, l'office des poursuites s'est référé à ses écritures cantonales et l'autorité cantonale n'a pas répondu. E. Par ordonnance du 17 avril 2013, la requête d'effet suspensif de la recourante a été admise, alors que celle tendant à l'octroi de sûretés de l'intimée a été déclarée irrecevable. 