Faits :
A.
A._ est propriétaire de la parcelle n° 29'437 de la commune de Conthey. D'une surface approximative de 3'000 m 2, ce bien-fonds est compris dans le secteur "Plan-Conthey-Le Parcouret". Ce périmètre, composé d'une trentaine de parcelles totalisant une surface d'environ 18'800 m 2, est encerclé par les routes de la Morge, à l'est, de Savoie, au nord, et la rue du Parcouret, au sud et à l'ouest; il est classé, pour partie en zone extension village et, pour le surplus, en zone mixte commerce et artisanat selon le plan d'affectation et le règlement communal des constructions et des zones (ci-après: RCCZ) approuvés par le Conseil d'Etat du canton du Valais le 10 juin 1997.
Ce bien-fonds se situe aussi dans le périmètre du remembrement parcellaire urbain du secteur Le Parcouret (RPU Le Parcouret), que la commune de Conthey a décidé d'exécuter le 2 juillet 2010. Le RPU Le Parcouret se trouve dans sa phase de mise en oeuvre proprement dite au sens des art. 33 ss de la loi cantonale concernant le remembrement et la rectification de limites du 16 novembre 1989 (LRRL; RS/VS 701.2). Un plan d'aménagement détaillé pour le secteur "Plan-Conthey-Le Parcouret" (PAD Le Parcouret) est entré en force le 11 janvier 2017 (à la suite de l'arrêt du Tribunal fédéral 1C_451/2016 du 11 janvier 2017).
La parcelle précitée figure encore dans le projet d'exécution routier en lien avec le remaniement parcellaire urbain Le Parcouret, homologué par le Conseil d'Etat le 20 décembre 2017. Le 5 février 2018, A._ a déposé un recours auprès du Tribunal cantonal du canton du Valais contre la décision du 20 décembre 2017 du Conseil d'Etat. La procédure est actuellement pendante devant le Tribunal cantonal.
B.
En décembre 2017, A._ a déposé une demande d'agrandissement du bâtiment (cave/dépôt) se trouvant sur la parcelle précitée. Le 14 décembre 2017, la commune de Conthey a informé A._ qu'elle devait transmettre le dossier à la Commission d'exécution du remembrement urbain du secteur "Le Parcouret" (ci-après: la Commission d'exécution) pour approbation, en vertu des art. 17 et 18 LRRL.
Par décision du 20 février 2018, la Commission d'exécution a refusé d'approuver le projet, au motif que celui-ci pouvait fortement perturber le projet routier homologué par le Conseil d'Etat le 20 décembre 2017, lié au RPU. Par décision du 13 mars 2018, la commune de Conthey a rejeté la demande d'autorisation de construire déposée par le recourant et classé le dossier sans suite, en transmettant la décision du 20 février 2018.
Par décision du 28 novembre 2018, la Commission de recours en matière agricole et de remaniements parcellaires du canton du Valais (ci-après: la Commission de recours) a rejeté le recours déposé par A._ contre la décision du 20 février 2018. Elle a considéré en substance que la décision de refuser le projet litigieux reposait sur l'art. 18 LRRL, qui permet à la Commission d'exécution de refuser l'approbation d'un projet de construction susceptible d'entraver l'exécution d'un remembrement parcellaire urbain; la Commission ayant relevé à bon droit que le projet de construction litigieux empiétait de quelque 2,7 m sur l'alignement de 6 m depuis l'axe de la desserte A, prévu par le PAD Le Parcouret et par le projet d'aménagement routier, homologué par le Conseil d'Etat le 20 décembre 2017, mais non entré en force.
C.
Agissant par la voie du recours en matière de droit public, A._ demande principalement au Tribunal fédéral de réformer la décision du 28 novembre 2018 en ce sens que le projet de construction litigieux est approuvé. Il conclut subsidiairement à l'annulation de la décision du 28 novembre 2018 et au renvoi de la cause à l'autorité précédente pour nouvelle décision au sens des considérants.
Le Service de l'agriculture du canton du Valais et la Commission d'exécution RPU Le Parcouret (Conthey) renoncent à se déterminer, alors que la Commission de recours renvoie aux considérants et au dispositif de sa décision.

Considérant en droit :
1.
Dirigé contre une décision finale (<ref-law>) prise en dernière instance cantonale (art. 86 al. 1 let. d LTF) dans le domaine du droit public (<ref-law>), le recours en matière de droit public est en principe recevable, aucune des exceptions prévues à l'<ref-law> n'étant réalisée. Le recourant a pris part à la procédure de recours devant l'instance précédente (<ref-law>). En tant que propriétaire de la parcelle concernée par le refus d'autorisation de construire, le recourant est particulièrement touché par l'arrêt attaqué. Il peut ainsi se prévaloir d'un intérêt personnel et digne de protection à l'annulation de l'arrêt attaqué. Il a dès lors qualité pour agir au sens de l'<ref-law>.
Les autres conditions de recevabilité sont par ailleurs réunies, si bien qu'il y a lieu d'entrer en matière sur le fond.
2.
Le recourant fait d'abord valoir une application arbitraire de l'art. 18 LRRL (art. 9 Cst.).
2.1. Le Tribunal fédéral ne revoit l'interprétation et l'application du droit cantonal et communal que sous l'angle de l'arbitraire. Une décision est arbitraire lorsqu'elle viole gravement une norme ou un principe juridique clair et indiscuté, ou lorsqu'elle contredit d'une manière choquante le sentiment de la justice et de l'équité. Le Tribunal fédéral n'a pas à déterminer quelle est l'interprétation correcte que l'autorité cantonale aurait dû donner des dispositions applicables; il doit uniquement examiner si l'interprétation qui a été faite est défendable. Par conséquent, si celle-ci ne se révèle pas déraisonnable ou manifestement contraire au sens et au but de la disposition ou de la législation cantonale en cause, elle sera confirmée, même si une autre solution paraît également concevable, voire préférable. De plus, il ne suffit pas que les motifs de la décision attaquée soient insoutenables, encore faut-il que cette dernière soit arbitraire dans son résultat (<ref-ruling> consid. 2.1 p. 18). Dans ce contexte, le recourant est soumis aux exigences accrues de motivation de l'<ref-law>.
2.2. A teneur de l'art. 18 al. 1 LRRL, pendant la procédure de remembrement, aucune modification juridique ou de fait ne devra être apportée aux immeubles compris dans le périmètre sans l'approbation de la commission d'exécution (territoire à ban). Cela signifie que durant la procédure de remembrement, aucune modification juridique ou de fait susceptible d'entraver le remembrement ne peut être apportée aux biens-fonds compris dans le périmètre (Bulletin des séances du Grand Conseil valaisan, session du 24 janvier 1989, p. 171).
2.3. Le recourant prétend que l'autorité intimée fonde sa décision sur le fait que le projet du recourant ne respecte pas l'alignement de 6 m par rapport à la route, ce qui découlerait du plan routier non entré en force. Il soutient qu'il est contradictoire de se fonder sur un plan d'affectation non entré en force pour refuser un projet de construction.
Ce grief peut être d'emblée rejeté, dans la mesure où l'alignement de 6 m par rapport à la route bordant le nord de la parcelle litigieuse est prévu par le PAD Le Parcouret, entré en force. Il est par conséquent soutenable de considérer que l'alignement prévu par le PAD Le Parcouret doit être respecté, ce d'autant plus que le plan d'exécution routier, certes non encore entré en force, prévoit le même alignement. L'instance précédente n'a donc pas fait preuve d'arbitraire en considérant que le projet litigieux pouvait être refusé sur la base de l'art. 18 LRRL, même si le plan d'exécution routier n'était pas exécutoire. Le grief doit ainsi être écarté.
3.
Le recourant se plaint ensuite d'une violation de la garantie de la propriété (art. 26 Cst.).
3.1. Les restrictions à la propriété ne sont conformes à l'art. 26 Cst. que si elles reposent sur une base légale, sont justifiées par un intérêt public suffisant et respectent le principe de la proportionnalité (art. 36 Cst.).
3.2. Le recourant prétend uniquement que l'art. 18 LRRL ne constitue pas une base légale suffisante justifiant la restriction à sa propriété car cette disposition ne fait que soumettre le projet litigieux à l'approbation de la Commission d'exécution. Il estime que l'approbation requise serait en réalité refusée sur la base du plan d'exécution routier, homologué le 20 décembre 2017 par le Conseil d'Etat, mais non entré en force.
Le recourant ne peut être suivi. En effet, il n'est pas contesté que le projet de construction litigieux empiète de quelque 2,7 m sur l'alignement de 6 m depuis l'axe de la desserte A, prévu par le PAD Le Parcouret et par le projet d'aménagement routier, ce qui entrave le remembrement tel que planifié à ce stade. Or l'art. 18 LRRL permet à la Commission d'exécution de refuser l'approbation d'un projet de construction susceptible d'entraver l'exécution d'un remembrement parcellaire urbain. La restriction à la garantie de la propriété repose ainsi sur une base légale formelle suffisante. Le fait que le plan d'exécution routier ne soit pas entré en force n'y change rien (voir supra consid. 2.2). Mal fondé, le grief de violation de l'art. 26 Cst. doit être écarté.
4.
Le recourant se plaint enfin d'une violation du principe de la coordination (art. 25a LAT), au motif que rien ne garantit que l'alignement de 6 m par rapport à la route bordant le nord de la parcelle litigieuse prévue par le PAD Le Parcouret figurera dans le plan routier qui n'est pas entré en force.
A teneur de l'art. 4 du règlement du PAD Le Parcouret, les alignements relatifs à la route de desserte sont identifiés. Le plan y annexé prévoit un alignement de 6 m. Quant au projet d'exécution routier "Le Parcouret", homologué par le Conseil d'Etat le 20 décembre 2017, il prévoit aussi un alignement de 6 m. Le projet d'exécution routier est ainsi conforme au PAD Le Parcouret, de sorte qu'il n'y a pas de décisions contradictoires au sens de l'art. 25a al. 3 LAT.
Au demeurant, l'art. 25a al. 1 LAT prévoit qu'une autorité chargée de la coordination est désignée lorsque l'implantation ou la transformation d'une construction ou d'une installation nécessite des décisions émanant de plusieurs autorités. Or en l'espèce il s'agit d'une autorisation de construire qui relève de la compétence exclusive de la commune, de sorte que l'on ne se trouve pas dans le champ d'application de l'art. 25a LAT.
Dès lors, le grief de violation de l'art. 25a LAT peut être rejeté.
5.
Il s'ensuit que le recours est rejeté, aux frais du recourant qui succombe (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est rejeté.
2.
Les frais judiciaires, arrêtés à 4'000 francs, sont mis à la charge du recourant.
3.
Le présent arrêt est communiqué au mandataire du recourant, à la Commission d'exécution du remembrement urbain du secteur "Le Parcouret", au Service de l'agriculture du canton du Valais et à la Commission cantonale de recours en matière agricole et de remaniements parcellaires du canton du Valais.
Lausanne, le 26 septembre 2019
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Président : Chaix
La Greffière : Tornay Schaller