Demnach erkennt das Bundesgericht:
1.- Die Verwaltungsgerichtsbeschwerde wird abgewiesen.
2.- Es wird dem Beschwerdeführer für das bundesgerichtliche Verfahren die unentgeltliche Rechtspflege gewährt:
a) Es werden keine Kosten erhoben.
b) Rechtsanwalt Dr. Markus Raess wird für das bundesgerichtliche Verfahren als amtlicher Rechtsvertreter bezeichnet und aus der Bundesgerichtskasse mit Fr. 1'500.-- entschädigt.
3.- Dieses Urteil wird dem Beschwerdeführer und dem Bundesamt für Polizeiwesen, Sektion Auslieferung, schriftlich mitgeteilt.
______________
Lausanne, 29. März 2000
Im Namen der I. öffentlichrechtlichen Abteilung
des SCHWEIZERISCHEN BUNDESGERICHTS
Der Präsident: Der Gerichtsschreiber: