If you want to process the parent before the children, you should move apply-templates to the end of your parent template:
<xsl:template match="Claim/Claimant">
<xsl:text>NM1*CC*1*</xsl:text>
<xsl:value-of select="@lastName" />
<xsl:text>*</xsl:text>
<xsl:value-of select="@firstName" />
<xsl:text>*</xsl:text>
<xsl:value-of select="@middleName" />
<xsl:text>*</xsl:text>
<xsl:text>*</xsl:text>
<xsl:value-of select="@suffixName" />
<xsl:text>*</xsl:text>
<xsl:value-of select="@indentificationCodeQualifier" />
<xsl:text>*</xsl:text>
<xsl:value-of select="@identificationCode" />
<xsl:text>~</xsl:text>
<xsl:text>
</xsl:text>
<xsl:apply-templates />
</xsl:template>
<xsl:template match="ClaimantStreetLocation">
<xsl:apply-templates />
<xsl:text>N3*</xsl:text>
<xsl:value-of select="@primary" />
<xsl:text>~</xsl:text>
<xsl:text>
</xsl:text>
</xsl:template>`
Update: What's happening here is:
The first element that is processed is Claim, but there are no templates matching it, so the default template applies, which process the templates for its children nodes.
There, the first child is Claimant, and you do have a template that matches it, so it is applied.
Next, that template is processed in order. But the critical point is that apply-templates omits the attributes in its default select (see What is the default select of XSLT apply-templates?), so the only matched node there is the ClaimantStreetLocation element.
Given that you have a template that matches ClaimantStreetLocation, it is applied. So, if you want to process first the attributes, you should delay the apply-templates until they are selected, in your case, manually.