Edit FASTA header using sed
awk 'BEGIN{FS="::"}{if($1~"&gt;"){printf("&gt;%s_%s\n",$2,substr($1,2))}else{print $0}}' input_file.fa &gt; output.fa


An explanation of the non-obvious bits:


BEGIN{FS="::"} split columns using :: as the designator
$1~"&gt;" If there's a > in the line
substr($1,2) Trim the &gt; that was at the beginning of the line.